2
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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)$$

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.