Question

Triology | CodeNation | Coding | OA | SDE | Set-3

Answer 1

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