We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Search all subsequences, check min0 and min1 where 0< min0 < min1 < data[i] to maximize y=min0^min1(simplified version of the original AND-XOR-OR expression).
2.How much time this takes?
o(n^2)
3.Once the beginning element of the intervel is no longer min0 or min1, then we can break the loop and move on.
e.g. with data 9 6 3 5 2, we check 9/6,9/6/3 and we don't need to check 9/6/3/5 and 9/6/3/5/2 any more and move on to 6/3, 6/3/5.... because the results will be the same.
4.How much difference does not make?
Best case, the input is sorted in decending order, then it's O(n);
Worst case, if the input is sorted in acending order, then it's still O(n^2)
5.Can we break the loop earlier?
What about we pre-process the data, mark if the data is smaller than everything to the right of it? If we have reached the smallest value amont the rest of the sequence, we can break.
6.Is it good?
No, consider case: 2 3 4 5 6 7 1, still O(n^2);
7.Anything that works?
Since each time we expand the interval to the right, our min0 and min1 updates if and only if the newly checked value is smaller than either or both of them.
So if we knew where that is, we can look it up and jump to it.
8.psudocode:
let n be number of elements
let v be data
let min0 and min1 be smallest and second smallest value between interval [i,j]
for i=1:n-1
for j=i+1:n
update min0,min1 using v[j];
if v[i] does not equal to min0 or min1
break the j loop;// rule #3 above
jump j to location l where v[l]<v[j] and j<l<n
For each i(start of the interval), the j(end of interval) won't jump more than twice, because rule #3 will kick in and break the loop and move on. Then this should be O(n), so is the subroutine to calculate the l table, so O(n) overall
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
AND xor OR
You are viewing a single comment's thread. Return to all comments →
Another way to think about this problem:
1.Naive approach:
2.How much time this takes?
3.Once the beginning element of the intervel is no longer min0 or min1, then we can break the loop and move on.
4.How much difference does not make?
5.Can we break the loop earlier?
6.Is it good?
7.Anything that works?
8.psudocode:
9.How do we know l?
10.Fast enough?