BIT2 - Search Bit Sum
Deepan is a palantir incredible guy who once had a trip in Switzerland. He saw a weird shop where he liked a teddy. But he didn't have enough dollars with him to buy this teddy. But there was a scheme ongoing like solve a equation and get the teddy and pay whatever we wish. That's why this shop is weirdo. He had no eager to buy this teddy as not many people can solve the equation, so he was sure he can get this teddy as soon as he solve the problem. He need your help to solve the equation. You will be given a number N, and you have to tell whether there exist a number K so that sum of BITS in all the numbers from 1 to K is equal to N. If there exist a K, then print it, else print "Does Not Exist." without quotes.
Constraints
1 ≤ N ≤ 1015, 1 ≤ T ≤ 105.
Input
First line contains t, number of test cases. For each test case, first line contains N.
Output
Output as described above.
Example
Input: 6 282657 377636 472615 567594 662573 1992279 Output: 38050 49299 Does Not Exist. Does Not Exist. 82953 227394
hide comments
|
mahmud2690:
2016-10-30 17:22:36
Nice problem! |
|
rainy jain :
2016-05-14 16:12:28
Is there any formula for log(n) approach?
|
|
geraji4122:
2015-09-19 15:48:45
i ac in log(n) |
|
Chandan Mittal:
2014-06-17 04:03:17
learnt just another new thing today
|
|
[Lakshman]:
2014-06-17 04:03:17
@fitcat Thanks. I checked my algo deeply and find the bug, Now AC with log n. |
|
newbie:
2014-06-17 04:03:17
my log(n)^2 giving tle....someone plz help...can log(n)^2 get accepted or i need to find some other algo Last edit: 2014-02-15 10:03:43 |
|
fitcat:
2014-06-17 04:03:17
Though I haven't looked into any O(log(n)^2) solutions, I believe and agree that O(log(n)) solution is much simpler. The logic is not hard and in fact quite easy.
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2014-06-17 04:03:17
@Lakshman: maybe my O(log(n)) approach is different than yours.. Last edit: 2014-03-08 12:37:19 |
|
|
[Lakshman]:
2014-06-17 04:03:17
@(Tjandra Satria Gunawan)(曾毅昆) some how I am able to write a log n algo but it overflows , and if I use python it gives tle. |
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2014-06-17 04:03:17
actually O(log(n)) solution is shorter & easier to implement than O(log(n)^2).. the hard part is to get the correct logic.. |
| Added by: | Rishav Goyal |
| Date: | 2014-02-07 |
| Time limit: | 1.223s-2.446s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
| Resource: | own |
RSS