HackerRank ‘Strange Counter’ Solution

Short Problem Definition:

Bob has a strange counter. At the first second, it displays the number 3. Each second, the number displayed by the counter decrements by 1 until it reaches 1.

The counter counts down in cycles. In next second, the timer resets to 2x the initial number for the prior cycle and continues counting down.

Link

Strange Counter

Complexity:

time complexity is O(log(N))

space complexity is O(1)

Execution:

This is a ‘simple’ mathematical problem that requires no while loops. First, find out what cycle the value T belongs to. Secondly, determine the value at the end of the cycle. Go back T steps to figure out the exact value at T.

Be careful, this can easily int overflow in C++, if the input is large enough.

Solution:
#include <bits/stdc++.h>

using namespace std;

// Complete the strangeCounter function below.
long strangeCounter(long t) {
    return 6 * pow(2, floor(log2((t+2)/3))) - 2 - t;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    long t;
    cin >> t;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    long result = strangeCounter(t);

    fout << result << "\n";

    fout.close();

    return 0;
}

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin