Super Hard Infosys OA Question | Harder than FAANG | Set - 12 | 2022 | October

Question

Answer 1

Read : Wipro Diwali Bonus  

Given an array nums of n integers. Delete a subsequence of length k (where k =n/3) from the array. Let's call the array B after deleting the subsequence. Now boy will be happy if the array B can be divided into 2 subarray of equal length such that difference between sum of elements of first subarray and sum of elements of second subarray is minimum possible. Boy asked you to make him happy. Note: It is guaranted that n is divisible by 3. Example 1: Input: nums = {7,9,5,7,2,1} Output: 3 Explanation: Delete the nums[2] and nums[6]. Then array B will be- {7, 5, 7, 2}. Now the array can be divided into {7,5} and {7,2}. So the answer will be (7+5)-(7+2) = 3. Example 2: Input: nums = {5,6,3} Output: -1 Explanation: Delete nums[3]. Then array B will be- {5,6}. Now the array can be divided into {5} and {6}. So the answer will be 5-6 = -1.

Contraints: 1<=n<=10^5

1<=nums[i]<=10^9

Answer 2

Efficient C++ Code : 

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef
tree<
  pair<int,int>,
  null_type,
  less<pair<int,int>>,
  rb_tree_tag,
  tree_order_statistics_node_update>
st;

typedef long long int ll ; 
ll g5[500005],v[500005];
ll a [200005]; 
ll rr = -1e18 ;
unordered_map <ll,ll> b ; 
unordered_map <ll,ll> kk ; 
unordered_map <ll,ll> u ; 

ll c[200000];
ll segtree[1000000];

void build(ll node,ll start,ll end)
{
    if(start==end)
    {
        segtree[node] = 0 ;  
        c[start] = 0 ;
    }
    else
    {
        ll mid=(start+end)/2;
        build(2*node,start,mid);
        build(2*node+1,mid+1,end);
        segtree[node]=segtree[2*node]+segtree[2*node+1];
    }
}

ll query(ll node,ll start,ll end,ll l,ll r)
{
    
    if(start>r || end<l)
    {
        return 0;
    }
    
    if(start>=l && end<=r)
    {
        return segtree[node];
    }
    
   
        ll mid=(start+end)/2;
        
        ll left=query(node*2,start,mid,l,r);
        ll right=query(node*2+1,mid+1,end,l,r);
        
        return (left+right);
        
    
    
}

void update(ll node,ll start,ll end,ll ind,ll value)
{
    if(start==end)
    {
        segtree[node]+=value;
        c[ind]+=value;
    }
    else
    {
        ll mid=(start+end)/2;
        
        if(ind<=mid)
        {
            update(2*node,start,mid,ind,value);
        }
        else
        {
             update(2*node+1,mid+1,end,ind,value);
        }
        
        segtree[node]=segtree[2*node] + segtree[2*node+1];
        
        
        
    }
    
    
    
}

int main() {
    
    ll n ;
    cin>>n ; ll w = 0 ; 
    ll i = 1 ; vector <ll> r ; 
    while(i<=n){
        cin>>a[i];w = w + a[i];
        kk[a[i]]++;
        r.push_back(a[i]);
        i++;
    }
    sort(r.begin(),r.end()) ; 
    
    i = 0 ; 
    while(i<r.size()) {
        b[r[i]] = i + 1 ; 
        i++;
    }
    st t ; 
    
     i = 1 ; 
    while(i<=n){
        
        update(1,0,200000,b[a[i]],a[i]) ; 
        
        u[a[i]]++;
        
        t.insert({a[i],u[a[i]]});
        
        //cout<<a[i]<<" "<<u[a[i]];
        //cout<<"\n";
        
         if(i>=n/3){
            
            
            
            ll count = i - n/3 ; 
           
            //cout<<i<<"\n";
            //cout<<count<<"\n";
            auto g = t.find_by_order(count-1);
            pair <int,int> r = *g ; 
            //cout<<r.first<<" "<<r.second ; 
            //cout<<"\n";
            
            
            ll ookk = r.first ; 
            
            ll sum = query(1,0,200000,0,b[r.first]-1);
            sum = sum + r.first*r.second ; 
            g5[i] = sum ; 
            //cout<<i<<" ";cout<<g5[i]<<"\n";
        }
        
        
        
        i++;
    }
    

    //cout<<"\n";
    u.clear();
    build(1,0,200000);
    t.clear();
    ll c = 1 ; 
    i = n ; 
    while(i>=1){
        
       update(1,0,200000,b[a[i]],a[i]) ; 
        
        u[a[i]]++;
        
        t.insert({a[i],u[a[i]]});
        
        //cout<<a[i]<<" "<<u[a[i]];
        //cout<<"\n";
        
         if(c>=n/3){
            
            
            
            ll count = c - n/3 ; 
           
            //cout<<i<<"\n";
            //cout<<count<<"\n";
            auto g = t.find_by_order(c-count);
            
            
            if(count!=0){
                
            pair <int,int> r = *g ; 
            //cout<<r.first<<" "<<r.second ; 
            //cout<<"\n";
            
            
            ll ookk = r.first ; 
            
            ll sum = query(1,0,200000,b[r.first]+1,200000);
            
            //cout<<"\n";
            //cout<<sum ;
            //cout<<"\n";
            
            
            sum = sum + r.first*(abs(r.second-kk[r.first]) + 1) ; 
            v[i] = sum ; 
            //cout<<i<<" ";cout<<v[i]<<"\n";
            } 
            else 
            {
                v[i] = 0 ;
                //RM_RM!!!!!!!!!
                //cout<<i<<" "<<v[i]<<"\n";
            }
            
            
            
        }
        
        
        c++;
        i--;
    }
    
    i = 1 ; 
    ll sum2 = a[1] ; 
    ll sum5 = w - a[1] ; 
    while(i<=n){
        
        ll y2 = i ; 
        ll y5 = n - i ; 
        
        if(y2>=n/3 && y5>=n/3){
            
            ll v2 = (sum2-g5[i]);
            ll v5 = (sum5-v[i+1]);
            
            
            
            //cout<<i<<" "<<g[i]<<" "<<v[i+1];
            //cout<<"\n";
            ll ans = v2 - v5 ; 
            //cout<<ans ; 
            //cout<<"\n";
            rr = max(ans,rr);
        }
        
        sum2 =  sum2 + a[i+1] ; 
        sum5 = w - sum2 ; 
        i++;
    }
    cout<<rr ; 
    
    
    
    return 0 ; 
}

Answer 3

Brute Force code : 

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll ; 
ll g[200005],v[200005];
ll rr = -1e18 ; 
int main() {
    
    ll n ;
    cin>>n ; ll w = 0 ; 
    ll a[n+1]={0};
    ll i = 1 ; 
    while(i<=n){
        cin>>a[i];w = w + a[i];
        i++;
    }
    
    
    
    i = 1 ; 
    while(i<=n){
        
        if(i>=n/3){
            
            vector <ll> t ; 
            ll j = 1; 
            while(j<=i){
                t.push_back(a[j]);
                j++;
            }
            sort(t.begin(),t.end());
            ll sum = 0 ; 
            j = 0 ; 
            ll diff = i - n/3 ; 
            while(j<diff){
                sum = sum + t[j] ; 
                j++;
            }
            
            g[i] = sum ; 
            cout<<i<<" ";cout<<g[i]<<"\n";
        }
        
        
        
        i++;
    }
    
    ll c = 1 ; 
    i = n ; 
    while(i>=1){
        
        if(c>=n/3) {
            
            
            
            vector <ll> t ; 
            ll j = i; 
            while(j<=n){
                t.push_back(a[j]);
                j++;
            }
            sort(t.begin(),t.end());
            reverse(t.begin(),t.end());
            ll sum = 0 ; 
            ll diff = (c-n/3);
            j = 0 ; 
            while(j<diff){
                sum = sum + t[j] ; 
                j++;
            }
            
            v[i] = sum ; 
            //cout<<i<<" ";cout<<v[i]<<"\n";
        }
        
        
        c++;
        i--;
    }
    
    i = 1 ; 
    ll sum2 = a[1] ; 
    ll sum5 = w - a[1] ; 
    while(i<=n){
        
        ll y2 = i ; 
        ll y5 = n - i ; 
        
        if(y2>=n/3 && y5>=n/3){
            
            ll v2 = (sum2-g[i]);
            ll v5 = (sum5-v[i+1]);
            
            
            
            //cout<<i<<" "<<g[i]<<" "<<v[i+1];
            //cout<<"\n";
            ll ans = v2 - v5 ; 
            //cout<<ans ; 
            //cout<<"\n";
            rr = max(ans,rr);
        }
        
        sum2 =  sum2 + a[i+1] ; 
        sum5 = w - sum2 ; 
        i++;
    }
    cout<<rr ; 
    
    
    return 0 ; 
}