Problem: LightOJ 1042 — Secret Origins
Link: http://lightoj.com/volume_showproblem.php?problem=1042
My Solution: http://ideone.com/jMD5fa
Give me some hints to avoid TLE.
Thanks
Problem Description:
This is the tale of Zephyr, the greatest time traveler the world will never know. Even those who are aware of Zephyr's existence know very little about her. For example, no one has any clue as to which time period she is originally from.
But we do know the story of the first time she set out to chart her own path in the time stream. Zephyr had just finished building her time machine which she named — "Dokhina Batash". She was making the final adjustments for her first trip when she noticed that a vital program was not working correctly. The program was supposed to take a number N, and find what Zephyr called its Onoroy value.
The Onoroy value of an integer N is the number of ones in its binary representation. For example, the number 13 (11012) has an Onoroy value of 3. Needless to say, this was an easy problem for the great mind of Zephyr. She solved it quickly, and was on her way.
You are now given a similar task. Find the first number after N which has the same Onoroy value as N.
Input
Input starts with an integer T (≤ 65), denoting the number of test cases.
Each case begins with an integer N (1 ≤ N ≤ 10^9).
Output
For each case of input you have to print the case number and the desired result.
Sample Input
5
23
14232
391
7
8
Output for Sample Input
Case 1: 27
Case 2: 14241
Case 3: 395
Case 4: 11
Case 5: 16
Hint: Use a greedy approach.
Time complexity: O(T * logN).
You may try with STL next_permutation
N is 10^9
Isn't use of next_permutation also gives TLE ?
Yes, that is why I told you to think of a greedy approach? Do you need to give you my code or you want to think again?
No. Don't give me your code.
Actually i didn't got you fully.Plz Tell me ,greedy approach means all possible calculation?
Okay! The idea is to store the reversed N's binary representation in a string S(1-based). After reversing it we'll add a '0' to the end of S. That won't change anything. Now, find the leftmost position i for which S[i]=1 and S[i+1]=0. Swap them and then sort S[1],S[2],...,S[i] in DECREASING order. Reverse the string S and now you have the binary representation of the answer.
Update: My code is here. I posted it just to make the things easier for you.
You can apply next_permutation on the binary representation of N (this representation uses less than 32 bits). Then transform it again to decimal.
According to this: http://www.sgi.com/tech/stl/next_permutation.html, the function is linear. I think you can say it is O(1) amortized, because if the function in called N! times, it will run in O(N!) and not in O(NxN!)
And you think that O(32!) is fast enough?
You only need to apply it once, not N times. Got AC with that.
next_permutation transforms the range of elements [first, last) into the lexicographically next greater permutation of the elements.
Because i need the immediate next greater value after N , thats why next_permutation call only ones here, right ?
Yeah, only once. Actually the last case (N = 8; 1000 in binary) is a good one, because you need to do one more thing before applying next_permutation. I will leave that so that you can figure it out.
Can you give us your code, please? It seems to be interesting :)
https://ideone.com/eMtgMs
Seems like I didn't understand your idea. Actually, that is the solution that I described but without next_permutation. :)
Why an extra 0 need to append after N's binary ?
Because as I told you you should find the first position i where S[i]=1 and S[i+1]=0. If there is no such position then the answer will contain one more bit than the initial number.
Edit: This was for Mehedi33
Consider N = 8, if you transform this to binary it will be 1000, if you apply next_permutation, the number you will get will be 1 (0001).
But, If you have the binary number in this way: 01000, you will get (10000) which is 16 (and also the desired answer)