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 2i 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).
2 Likes
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!!
1 Like