Today I had CodeNation coding round (on-campus):
Question1 : Give an array a of size n where
1<=n<=100000
1<=a[i]<=200000
We need to find out for each i number of other j such that either =0ai%aj=0 or =0aj%ai=0....
Example : 4 2 1 3
output : 2 2 3 1
We can solve it in O(nlogn) by using concept of harmonic series.
Question2 : Given tree of size n,
1<=n<=100000 , indexed from 0, rooted at node 0 and each node having distinct value from 0 till n-1. Find mex of each subtree.
Example : n=3 , edges : (0,1),(0,2) and values : v[0]=0, v[1]=1, v[2]=2. Output : mex[0]=3,mex[1]=0,mex[2]=0.
Was able to solve partially in O(n∗n). Can someone tell how to solve in better complexity ?
Question3 : Given an array a of size n, beauty from l to r is defined as : +(−1)∗+1++2+(−1)∗+3....a[l]+(−1)∗a[l+1]+a[l+2]+(−1)∗a[l+3]....repeating till r. 1<=<=141<=n<=1e4. There are Q queries,
1<=n<=10000
1<=Q<=200000
Either 1 i x, which means update a[i]=x, or 2 L R, which means maximum beauty among all subarrays in index range L to R.
Note that :
x>=-1000000000
a[i]<=1000000000