I recently participated in codeforces div-2 and I got Stuck at this THIS PROBLEM can anyone explain, how to solve this problem. I also referred to codeforces editorial but I couldn’t understand.

I solved this problem by observing the pattern where each number would come. For example 1 comes at position 1,3,5 and 2 comes at 2,6,10 so a number in range 1 to 50 comes at positions which are in AP with a common difference 2^{i} and the first element of that AP is always 2^{(i-1)} where i is the number [1,50] . Now for any k as input you have 50 distinct AP and you can easily check that this k falls in which one.

A more simpler approach would be if k is odd then simply k th place would be occupied by 1.

Now if k=2,6,10,14… then you can understand dividing these number by 2 will be an odd number and note middle number is always be a odd number . So in this case our answer would be 2. Similarly we keep on dividing k by 2 until we get an odd number and result the count as an answer how many times we have divided k by 2.

Two lines of code would be

int ans=1;

while(k%2==0) k/=2,ans++;

return ans;

Hope this will help.

Happy Coding

It can also be solved using binary search as if *K* is equal to the mid position of the sequence then *n* will be the answer otherwise if *K* is greater, then *K* must be present in the right half of the sequence, so we will change our left limit to *mid+1*, else if *K* is smaller, we will change our right limit to *mid-1* and in each iteration we will decrease *n* by one.

For implementation details, you can see my solution (link).

I think I got a relation that the number is the last non-zero bit from the binary representation of k. Though I couldn’t find it during the contest.

this was my answer…it got accepted

Hope this helps!!