Strange Counter | Hackerrank Problem Solution With Explanation

Problem Statement

There is a strange counter. At the first second, it displays the number . Each second, the number displayed by decrements by 1 until it reaches 1. In next second, the timer resets to 2 x the initial number of the prior cycle and continues counting down. The diagram below shows the counter values for each time t in the first three cycles:

Find and print the value displayed by the counter at time t.

Input Format
A single integer, the value of t.

Sample Input
4

Sample Output
6

Link to question: https://www.hackerrank.com/challenges/strange-code/problem

Solution (Python3)

def strangeCounter(t):

    # Write your code here

    n = math.log(((t + 3) / 3), 2)

    if math.floor(n) == math.ceil(n):

        return 1

    n = int(math.ceil(n))

    term = 3 * (math.pow(2, n) - 1)

    return int(term - t + 1)

Explanation

From the given problem statement, we can clearly see that:

Time taken to complete 1st cycle: 3s
Time taken to complete 2nd cycle: 6s
Time taken to complete 3rd cycle: 12s

And so on.

If we observe a little bit then we will find that time taken by cycles is forming a series and that series is in G.P. (Geometric Progression) with common ratio as 2.

It is clear that the time at which is any cycle ends, is the cumulative sum of all the time taken to complete the cycle till that cycle. Viz.

Time at which 1st cycle ends: 3
Time at which cycle ends: Time taken to complete 1st cycle + Time taken to complete 2nd cycle = 3 + 6 = 9

And so on.

If this series is in G.P. then the cumulative sum, i.e. the end time for any cycle, can be calculated using the below formula:

S = a(rⁿ-1)/(r-1),

where S is the sum of the series, a is the first term of the series, r is the common ratio and n is the number of terms in the series.

Here, in the problem, we are given the sum of the series (i.e. t in this case), we know the first term and the common ratio (i.e. 3 and 2). So, we have to calculate n. Using the above formula, we can deduce:

n=log₂((S+3)/3)

If we get a whole number as n then given t is the end time of the cycle. But if we get a floating number, then t is the time between the end times of previous cycle and next cycle. In this case, using the ceil value of t and the formula of the Sum of G.P. we can calculate the end time for the current cycle, say terms. And the difference between the terms and the t is our answer.