Sunday, September 18, 2016

Geometric Counter


Problem: https://www.hackerrank.com/challenges/strange-code
Solution:
Consider the following geometric progression (G.P.): 3,6,12,24,... with first term a = 3 and common ratio r = 2. Some basics
nth term of GP: $$a_n = ar^{n-1}$$
Solving, $$\frac{a_n}{a} = r^{n-1}$$
Taking log of both sides: $$\log_2 \frac{a_n}{a} = (n-1)\log_2 r$$
Now looking at the sample input, it can inferred that the given input t is the sum to nth term of the above GP.
Sum to n terms of GP: $$S_n = a\frac{1 - r^n}{1-r}$$ Solving the above equation,
$$S_n\frac{1-r}{a} = 1 - r^n$$ $$=> r^n = 1 - S_n\left(\frac{1-r}{a}\right)$$ Taking log of both sides:
$$=> n\log_2 r = \log_2 \left(1 - S_n\frac{1-r}{a}\right)$$ $$=> n = \frac{\log_2 \left(1 - S_n\frac{1-r}{a}\right)}{log_2 r}$$ "power" variable in the below program is the n to which the sum has been given as input.
After finding the value of n, we need to find the difference between the given input and the sum to the nth term. The "diff" variable in the below program is that difference.
Then observation on the sample input shows if diff is 0, the next iteration of the counter starts at that point, so the output will be 1. Else, the difference between the (n+1)th term and the input plus 1 is the output.

Java Program:
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

int main(){
    long long t;
    cin >> t;
    double tmp = t*(1-2)/3;
    double numerator = 1-tmp;
    int power = log(numerator)/log(2.0);
    long long sum = 3*(1-pow(2, power))/(-1);
    long long diff = t - sum;
    if(diff == 0) {
        cout<<"1"<<endl;
    }
    else {
        long long nextTerm = 3*pow(2,power);
        cout<<nextTerm - (diff - 1)<<endl;
    }
    return 0;
}

2 comments: