Problem: Strange Counter

Problem from Hackerrank
*Difficulty: Easy
Bob has a strange counter. At the first second, t = 1, it displays the number 3. At each subsequent second, the number displayed by the counter decrements by 1.

The counter counts down in cycles. In the second after the counter counts down to 1, the number becomes 2x the initial number for that countdown cycle and then continues counting down from the new initial number in a new cycle. The diagram below shows the counter values for each time t in the first three cycles:

Given a time, t, find and print the value displayed by the counter at time .

Input Format

A single integer denoting the value of t.


  • 1 <= t <= 10^12 (10 to the power of 12)


  • for of the maximum score.

Output Format

Print the value displayed by the strange counter at the given time .

Sample Input


Sample Output



Time marks the beginning of the second cycle in which the counter displays a number that is double the initial number displayed at the beginning of the previous cycle (i.e., ). This is also shown in the diagram in the Problem Statement above.

*How to solve:
The values at the top of each cycle are 3,6,12,24,… so you can easily find these values by multiply 3 to 2 multiple times. And the time at top is 1,4,10,22,… you can instantly see that time t is equal top value at each cycle minus 2.
1 = 3-2
4 = 6-2
10 = 12-2
…so on
with this in mind, you can create a list involving all the time at top of each cycle:
Screen Shot 2016-08-30 at 6.02.15 PMHere the biggest input is 10^12, so we have to create a list big enough to cover this number, 45 is large enough.
Then you can go through all elements in the list, if t is exactly the value at that element, we simply print out dic[i]+2 (see the explanation above). Otherwise, we seek for the first element bigger than t, because we know that, t is inside the cycle that  the top is the value of that element. For example:
t = 7, the list is 1,4,10,22
We loop to 10, because 10 is the first element bigger than 4, so we stop right there. With top = 4, the value at the top is 4+2 = 6. The value we’re looking for is: 6-(t-top), you got the idea.
Screen Shot 2016-08-30 at 6.38.19 PM