# HackerRank Strange Counter

I wrote a solution to HackerRank Strange Counter:

The counter counts down in cycles. At t = 1, the counter displays the number 3. At each subsequent second, the number displayed by the counter decrements by 1.

Each time the counter reaches 1, the number becomes 2× the initial number for that countdown cycle.

The sequence goes:

3, 2, 1, 6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, …

Print the value of the counter the time t, where 1 ≤ t ≤ 1012. For example, if t = 4, print 6.

My code works for inputs up to 100 million but when I enter number 1 billion or greater then I get TLE.

#include<stdio.h>
#include<iostream>

using namespace std;

int main()
{
long long n;

cin >> n;

long long  x = 3;
long long count = x;
for(long long i = 2; i <= n;i++)
{
count--;
if(i == n)
{
break;
}

else if(count == 1)
{    i++;
x = 2*x;
count = x;

}
}

cout << count;

return 0;
}


## Style

In C++, don't #include<stdio.h> or any other C-style .h file. #include <iostream> should be sufficient for all of your I/O needs. It is customary to put a space after #include.

In general, using namespace std is bad practice. Here, you actually wasted more characters writing the "shortcut" than writing out std::cin and std::cout like you should have.

In the problem statement, the input is called t. Why did you name your variable n in your code then?

x is a cryptic variable name. I suggest countdown_init.

It is customary to end the output with a newline. If you don't, then in Unix shells the command prompt would immediately follow the output on the same line, which looks ugly.

## Algorithm

The reason your program exceeds the time limit is simple: this loop counts up to n, one step at a time.

for(long long i = 2; i <= n;i++)


Your algorithm is thus said to be O(t).

To speed it up, you need to fast-forward through entire countdown sequences.

#include <iostream>

int main() {
long long countdown_init, t;
std::cin >> t;
for (countdown_init = 3; t > countdown_init; countdown_init *= 2) {
t -= countdown_init;
}
std::cout << (countdown_init - t + 1) << '\n';
}


This solution would be O(log t), since it only loops once per countdown cycle. We can estimate the amount of work by rounding up t to the last t of each cycle:

\begin{align} t \approx&\ 3\ (\underbrace{1 + 2 + 4 + \ldots + 2^{c}}_{c\ \textrm{cycles}}) \\ \approx&\ 3 \cdot 2^{c+1} \\ =&\ 6 \cdot 2^c \end{align}

The number of cycles $c$ is therefore

$$c \approx \log_2 \frac{t}{6} = O(\log t)$$