How? Can you please explain your approach…
like in 2nd you put every index of no of odd frequency in some array and after sorting you find min length subarray where all no are present atleast one time…
like in 4th one you just need to put the all possible values in some array and after sorting that array you need to find the min length subarray where all n indexes are present …at last the min value is the value at start index of the min length subarray and max value is the value at end index of that subarray
2 Likes
Did anyone face any issues with the compiler of 4th question?
2 Likes
no there is no issue I guess
Yes. Even I faced the issue.
the 3rd question had n<=0 valued 6 test cases, thats why many were stuck at 9/15…not expected from codenation…
3 Likes
By BST you mean self balancing BST ? Because in case of skewed BST, the time complexity for insertion and querying will be O(n) per operation.
For the second question BITLAND, I used the following algorithm :-
Finding all the numbers which have odd frequency and then, finding the two pair of numbers from all the odd frequency numbers whose distance is minimum, To find that , for each pair, i traversed the string and find the indices which are having in them those two values and are minimum distance apart.
Doing this for every pair of number would give me the best first and last value to be removed.
I got 4/15 test cases correct, can anyone suggest me where i am going wrong ?
I did the same thing…and also got the same score 4/15…I think my approach is correct…there may be some cases when it impossible to generate that number…but idk what is that condition…
PS: my approach may be wrong…
Did you managed to pass entire test set?
yup, and not only me but some of my frnds also face.
Can you tell the complexity of 4th one ?
O(nlogk) …(20 chars)
I used a completely different approach (The starting is same though), I find the frequency of all the numbers, then for all the numbers with an odd freq, I make a string out of it. Now I want to delete all the elements in the string p (My generated string) , from string a(Input string), Or I can say i need to find the minimum substring of a, that contains all the elements of p, This is a pretty common question and can be done using sliding window
For Eg:
a = 2113
p = 23
The minimum substring that contains 2 and 3 is 2113, I will print length of this substring - 1= 3
if
a = 2221131133
p = 23
The minimum substring containing 2 and 3 is 2113 (again) so I print len-1 = 3
Here’s the code, All TC passed https://ideone.com/40jjV3/
2 Likes
Can i get the problems link??
You don’t need segment tree for the last problem. You can solve it in O(n).
First create the Manacher array, and then precalculate the longest palindrome for each prefix (and suffix) with two pointers.
3 Likes
Yes.
For the 3rd problem (the tree problem):-
The main observation is that you have to select 2 nodes (lets say i and j ) with the maximum number of set bits in their binary representation. Then the answer is just their sum (xi+xj, where x1 and x2 are the numbers of set bits in decimal rep. of i and j).
There are 2 ways of doing this :
- Either use Digit DP on the binary form of given N.
- Or we can make some useful observations and we see that the optimal answer will always be: min( d1+d2-1, d1+x-1, 2*d1-3), where d1 is the MSB of N, d2 is the 2nd most significant set bit in N, and x is the number of set bits in N.
What was your approach for 5th question?. I solved it using square root decomposition.