## 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.