I have been looking at various solutions for this problem but couldn’t understand any of them.
So could anybody explain their approach to solving this problem?
I have been looking at various solutions for this problem but couldn’t understand any of them.
So could anybody explain their approach to solving this problem?
There was a question which demanded the same. link to question. if you are not able to figure it out after reading the answers feel free to ask.(always please check if there is any relevant question before posting yours)
Could you please give a proof to your solution? I am unable to prove that your method gives the correct solution. Thanks!
it is a very good question which requires just a little bit of observation…
you can see that each char at position 2^i is a so if you have to give query which is in the form of power of two simply print a.
lets define max as power of two just equal or less than desired position.
Now what happen if the number is not of type of power of two then there are two possibilities:-
i have written a simple two line fuction ,u can refer here
MY_ Solution
@deepcpp
My code-
int getans(ll k, ll pow) {
if(k==1)return 1;
if (k == (1 << (pow - 1))) return 1;
if (k < (1 << (pow - 1))) return getans(k, pow - 1);
else return -getans((1 << pow) - k, pow - 1);
}
This function will return 1 if the answer is a ans, will return −1 if the answer is c. I am just back doing the problem statement. You should call getans(k,63). complexity O(logN)…
Explanation-
My function $getans(K,pow)$represents K^{th} character in S_{pow}.
there may arise some cases when we call getans(K,pow):-
if K==1 the answer is 1,(i.e. 1st position will always have charcter ‘a’)
also S_{pow} will have length 2^{pow}-1.
S_{pow} will have same characters as S_{pow-1} for first 2^{pow-1}-1 characters.(as S_{pow} = S_{pow-1} + ‘a’+ rev1(rev2(S_{pow-1})) )
so if(K<2^{pow-1})(i.e. K is before middle position) i call getans(K,pow-1);
also S_{pow} will have “a” at $2^{pow-1}$th character.(as 2^{pow-1} is the middle position)
that’s why i return 1, when K==2^{pow-1}
also when i call getans(K,pow) and K>2^{pow-1}(i.e. K is after middle position) then we can relate some how K with S_{pow-1}.
we have to find out which position of S_{pow-1} will relate with K, if we reverse S_{pow-1} and add with itself with letter ‘a’ in between. clearly K will be related to 2^{pow}-K (i.e. distance from last =distance from first) (i.e. total length+1 - current Position)
(for ex "123404321" in this 1234 is reverse and added with itself with a 0 in between, so 2nd 3's position can be related to 1st 3's position as 1st 3's position = total length+1- 2nd 3's position.
here in our example 1st 3's position is 3, 2nd 3's position is 7, total length is 10)
so when k>2^{pow-1} i call -getans(2^{pow}-K,pow-1)
(-ve sign is added as all ‘a’ are reversed to ‘c’ and vice-versa)
done…
added bro…