HackerRank Strange Counter

Question

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 ≤ 10¹². 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;
}

200_success · Accepted Answer · 2016-11-19 19:17:09Z

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

Stack Exchange Network

HackerRank Strange Counter

1 Answer 1

Style

Algorithm

You must log in to answer this question.

Hot Network Questions

HackerRank Strange Counter

1 Answer 1

Style

Algorithm

You must log in to answer this question.

Related

Hot Network Questions