Question

Hackwithinfyi | Infosys | OA Coding Questions and Solutions | Set - 2 | 2022

Answer 1

Question : 

Find the subsequence from an array with highest score. Score is the sum of f(x) for all the elements of the subsequence. 

f(x) = number of divisors of 'x'. 

For , a[i] and a[i+1] in the selected subsequence , one of the following should be true : 

a[i] = 2*a[i+1]

or

a[i] = 3*a[i+1]

or 

a[i] = a[i] + 1 or a[i] = a[i] - 1 

or 

a[i] = a[i]/3 ( must be divisible by 3)

or 

a[i] = a[i]/2 ( must be divisible by 2) 

Input : 

10
2 3 4 5 6 12 18 36 9 99 

Output :  

28

[2,3,4,5,6,12,36] is the selected subsequence from the array [2+2+3+4+2+7+8==28]

My code : 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll ; 
ll divi[200006];
ll fin[200005];
void findDivisors(ll n)
{
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * i <= n; j++)
            divi[i * j]++;
    }
}

int main()
{
    ll r = 0 ; 
    int n = 100000+7;
    findDivisors(n);
    cin>>n;
    int i = 1 ; 
    while(i<=n)
    {
        int x ; 
        cin>>x ; 
        ll current = divi[x] ; 
        ll maxi = 0 ; 
        if(x%2==0)
        {
            maxi = max(maxi,fin[x/2]);
        }
        if(x%3==0)
        {
            maxi = max(maxi,fin[x/3]);
        }
         maxi = max(maxi,fin[x-1]);
         maxi = max(maxi,fin[x+1]);
         maxi = max(maxi,fin[2*x]);
         maxi = max(maxi,fin[3*x]);
        ll answer = current + maxi ; 
        fin[x] = max(fin[x],answer);
        //cout<<fin[x]<<'\n';
        r = max(fin[x],r);
        i++;
    }
    cout<<r ; 
    return 0;
}