Solving Strange Counter in O(1)


Strange Counter problem is an easy problem found in HackerRank. An intuitive solution to this problem seems to have logarithmic complexity. However I wanted to give an alternative solution with complexity of \(\mathcal{O}(1)\).

The problem statement can be found on the website, but is basically as follows:


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 \(2\times\text{the initial number of prior cyle}\), 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\).


The Solution

Now providing the solution by first formalizing it.


Definitions

Let \(F(t)\) be the value displayed by the counter at time \(t\), that is what we eventually want to compute as efficiently as possible.

Let \(P(t)\) be the index of the period of the value of at time \(t\). For example at time \(1\) to \(3\) timer is in first cyle. While at time \(4\) to \(9\) timer is in second cyle etc.

That is, e.g \(P(10), P(11), \dots P(21) = 3 \).

Let \(L(p)\) is the total length of the period \(p\). e.g \(L(1)=3,L(2)=6,L(3)=12\).

Let \(T(p)\) be the first time of the cyle \(p\), e.g \(T(1)=1,T(2)=4,T(3)=10\).

And similary \(V(p)\) be the first value of the cyle \(p\), e.g \(V(1)=3,V(2)=6,V(3)=12\).


Seeing The Solution

Then, suddenly everything becomes easy. The solution is the following:

$$F(t)=V(P(t)) - (t-T(P(t))) \tag{1}$$

That is, first we can find the index of the value at corresponding cyle by \((t-T(P(t)))\), then substracting it from the first value of the period gives us the answer.


Solving Each Function

\(L(p)\) can be defined as $$ \begin{array}{lcl} L(1) = 3 \\ L(n) = 2.L(n-1) \end{array} $$

Then, $$ \begin{array}{lcl} L(n) = 2.L(n-1) \\ L(n-1) = 2L(n-1-1) \\ L(n-1) = 2.L(n-2) \end{array} $$ If we substitute \(2.L(n-2)\) with \(L(n-1)\) at equation above, $$ \begin{array}{lcl} L(n) = 2.L(n-1) \\ L(n) = 2^2.L(n-2) \end{array} $$ if we continue this substitution, for every positive integer \(i>1\), $$ L(n) = 2^i.L(n-i) $$ For \(n-i=1\), after substitution \(n-i\) with \(1\) we have, $$ \begin{align} i&=n-1 \\ L(n) &= 2^i.L(n-i) \\ L(n) &= 2^{n-1}.L(n-(n-1)) \\ L(n) &= 2^{n-1}.L(1) \\ L(n) &= 3.2^{n-1} \tag{2} \end{align} $$


First time of the period \(p\), which is \(T(p)\), is equal to last time of the previous cycle plus 1 obviously. $$ \begin{align} T(1) &= 1 \\ T(n) &= T(n-1) + L(n-1) \\ \end{align} $$ and by equation (1), we have $$ \begin{align} T(1) &= 1 \\ T(n) &= T(n-1) + 3.2^{n-2} \\ \end{align} $$ and after solving the recurrence $$ \begin{align} T(n) &= 3.2^{n-1} - 2 \tag{3}\\ \end{align} $$


After observing \(T(n)\) and \(V(n)\), we found that: $$ \begin{align} T(n) + V(n) &= T(n+1) \\ \end{align} $$ Therefore, $$ \begin{align} V(n) &= T(n+1)-T(n) \\ V(n) &= (3.2^{n} - 2)-(3.2^{n-1} - 2) \\ V(n) &= 3.(2^{n}-2^{n-1}) \\ V(n) &= 3.2^{n-1} \tag{4} \\ \end{align} $$


Lastly \(P(n)\) can be derive from \(L^{-1}(n)\). Skipping intermediate steps, for every time \(t > 3\), we have: $$ \begin{align} P(n) &= \lfloor log_2(\lceil\frac{n}{3}\rceil)\rfloor + 1 \tag{5} \\ \end{align} $$


and by equations (1),(2),(3),(4), and (5): $$ $$ \begin{align} F(n) &= V(P(n)) - (n - T(P(n))) \\ F(n) &= V(\lfloor log_2(\lceil\frac{n}{3}\rceil)\rfloor + 1) - (n - T(\lfloor log_2(\lceil\frac{n}{3}\rceil)\rfloor + 1)) \\ F(n) &= 3.2^{\lfloor log_2(\lceil\frac{n}{3}\rceil)\rfloor} - (n - T(\lfloor log_2(\lceil\frac{n}{3}\rceil)\rfloor + 1)) \\ F(n) &= 3.2^{\lfloor log_2(\lceil\frac{n}{3}\rceil)\rfloor} - (n - 3.2^{\lfloor log_2(\lceil\frac{n}{3}\rceil)\rfloor}-2) \\ F(n) &= 6.2^{\lfloor log_2(\lceil\frac{n}{3}\rceil)\rfloor} - n - 2 \\ \end{align} $$ $$

and thats it.


Computational Complexity

Trivially both \(f(x)=2^x\) and \(g(x)=log_2x\) functions have complexity of \(\mathcal{O}(1)\) under uniform cost criteria for RAM computers.

Therefore, Strange Counter problem is computable with constant time-space complexity.