18 September 2016

Strange Counter

Standard
Bob has a strange counter. At the first second, , it displays the number . At each subsequent second, the number displayed by the counter decrements by .
The counter counts down in cycles. In the second after the counter counts down to , the number becomes  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  in the first three cycles:

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

Hints:


  • The last  'time' value of cycle 1 is 3 which is 3*1=3*(2^1-1).
  • The last 'time' value of cycle 2 is 9 which is 3*3=3*(2^2-1). 
  • The last 'time' value of cycle 3 is 21 which is 3*7=3*(2^3-1).
So, we will use a while loop and keep doubling n, which will represents  2^1, 2^2, 2^3 part. The loop stops when it reaches to a cycle whose max time is bigger than the real time t, then we know that it has reached the last cycle.
For example :
In the second cycle,  time =7 has value=3, and the max time of the second cycle is 9. We find the relationship between them is 3 = 9 - 7 + 1, which is why we print (3 * (n - 1) - t + 1) to get the output of 3 when t is 7.

Here is my code:

#include <iostream>using namespace std;

int main(){   

     long long t,n=2;

    cin >> t;

    while(3*(n-1)<t)n*=2;

    cout<<3*(n-1)-t+1<<endl;

    return 0;

}





 Question source:- hackerrank.com

9 comments: