Google sde internship problem

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
3 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

View all →

→ Find user

→ Recent actions

Detailed →

_thewiper_'s blog

Google sde internship problem

By _thewiper_, history, 3 years ago, In English

eleph_2323 1m Can someone help me in the following problem Given an array consisting of n integers and q queries. And in each query there is an integer x for which you need to report that is there any number in the array such that its bitwise and with x is zero. 1<=N,Q<=10^5,1<=arr[i]<=10^9

I tried doing this problem using Trie but couldn’t get the most optimised solution. Can someone help.

_thewiper_
3 years ago
20

Comments (19)

Show archived | Write comment?

raj_bansal

3 years ago, # |

Can you share the problem link?

→ Reply

raj_bansal

3 years ago, # |

-9

Firstly we can find the bitwise-OR of all elements(say ORall) in the array and for every set bit in ORall the array, we can store one element which has this bit set. And for every query, if (q=x&ORall>0 we can find the element corresponding to any set bit in q). I think this can work

→ Reply

_thewiper_

3 years ago, # ^ |

I don't think this will work because let's say x is 110010=50 So in array we need to find a number whose 2nd,5th and 6th bit should have 0.Now there can be multiple elements whose one specific bit is not set So we need to take intersection of elements whose 2nd,5th and 6th bit is not set This will result in O(n) time per query which will give tle.

→ Reply

CvYaswanth

3 years ago, # |

-41

You can use Trie Data Structure to solve this problem.

→ Reply

ashty243

3 years ago, # |

-17

This is a variation of this question and can be easily solved using Trie. You just have to think about what changes should be made to handle AND instead of XOR.

→ Reply

YPK

3 years ago, # ^ |

They are absolutely unrelated.

→ Reply

ashty243

3 years ago, # ^ |

Sorry, if you find it unrelated but I have solved only this problem related to this xor-trie concept and I was able to figure out the fully accepted solution to above mentioned problem in the blog in my google coding round.

→ Reply

Samarth12

3 years ago, # |

Are you sure that $$$arr[i] \leq 10^9$$$ ? The exact problem(except constraints on $$$arr[i]$$$) has been discussed here.

→ Reply

_thewiper_

3 years ago, # ^ |

Sorry i wrote constraints on A[i] .And yes the questions are same as in the blog

→ Reply

Ayrt_Samurai51296

3 years ago, # |

If $$$arr[i]<=10^6$$$ then this problem is same as this one https://codeforces.net/contest/165/problem/E .Not quite sure if preprocessing can be done for values upto $$$10^9$$$

→ Reply

satvikb

3 years ago, # |

This question has surfaced many times in a past few days, this problem can be solved using SOS DP easily. The link for the codeforces blog on SOS DP is available easily, just google SOS DP.

for the solution, here is the code that I wrote.

Code

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back
#define ppb pop_back
#define mp make_pair
using pi = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vector<int> >;
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()

//const int inf = 9e18;
const int NUM=1000030;
const int N = 10000000;
vector<int> lp, sieve;
vector<int> pr;
void primefactor();
int binpow(int a, int b);
int binpow(int a, int b, int mod);
int gcd(int a, int b);
int lcm (int a, int b);
bool comp(int a, int b);
int inversemod(int a, int mod);
void calc_sieve();

void test()
{
    int n, q;
    cin>>n>>q;
    vi exist((1<<20), 0);
    vi arr(n);
    for(int i=0;i<n;i++) cin>>arr[i];
    for(int i=0;i<n;i++) exist[arr[i]]=1;
    int maxpower=(1<<20)-1;
    for(int i=0;i<=maxpower;i++) 
    {
        for(int j=0;j<20;j++) 
        {
            if((i&(1<<j)) && exist[i-(1<<j)]) exist[i]=1;
        }
    }

    for(int i=0;i<q;i++) 
    {
        int a;
        cin>>a;
        if(exist[a^maxpower]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

signed main()
{
    //  freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--) test();
    return 0;
}

void calc_sieve() //credits: Anish_Sofat
{
    sieve.resize(NUM+1,0);
    for (int x = 2; x <= NUM; x++)
        {
            if (sieve[x]) continue;
            for (int u = x; u <= NUM; u += x)
            {
                    sieve[u] = x ;
            }
        }
}

void primefactor()
{
    lp.resize(N+1,0);
    for (int i=2; i<=N; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back (i);
        }
        for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
            lp[i * pr[j]] = pr[j];
    }
}

int binpow(int a, int b)
{
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

int binpow(int a, int b, int mod)
{
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a)%mod;
        a = (a * a)%mod;
        b >>= 1;
    }
    return res%mod;
}

int gcd(int a, int b)
{
    if(b==0) return a;
    else return gcd(b,a%b);
}

int lcm (int a, int b)
{
    return ((a / gcd(a, b)) * b);
}

bool comp(int a, int b)
{
    return a>b;
}

int inversemod(int a, int mod)
{
    return binpow(a,mod-2, mod);
}

Please mind the template, it is a bit cluttered.

→ Reply