HackerRank: Red John is Back

HackerRank: Red John is Back

Red John has committed another murder. But this time, he doesn't leave a red smiley behind. What he leaves behind is a puzzle for Patrick Jane to solve. He also texts Teresa Lisbon that if Patrick is successful, he will turn himself in. The puzzle begins as follows.

There is a wall of size 4xN in the victim's house. The victim also has an infinite supply of bricks of size 4x1 and 1x4 in her house. There is a hidden safe which can only be opened by a particular configuration of bricks in the wall. In every configuration, the wall has to be completely covered using the bricks. There is a phone number written on a note in the safe which is of utmost importance in the murder case. Gale Bertram wants to know the total number of ways in which the bricks can be arranged on the wall so that a new configuration arises every time. He calls it M. Since Red John is back after a long time, he has also gained a masters degree in Mathematics from a reputed university. So, he wants Patrick to calculate the number of prime numbers (say P) up to M (i.e. <= M). If Patrick calculates P, Teresa should call Red John on the phone number from the safe and he will surrender if Patrick tells him the correct answer. Otherwise, Teresa will get another murder call after a week.

We can convert the first part of the problem into a recurrence relation i.e. F(N) = F(N-1) + F(N-4) with the base case : F(0) = F(1) = F(2) = F(3) = 1.
Here, F(N) represents the number of ways of tiling the 4xN rectangle with 4x1 and 1x4 tiles. The explanation goes as :
If we place a 4x1 tile, then we just need to solve for F(N-1).
If we place a 1x4 tile, then we can't place a 4x1 tile under it. Basically, we will have to place a set of four 1x4 tiles together, hence we solve forF(N-4).

Finally, we take the sum and get the total number of configuration i.e. M.

Once we get M, we need to to calculate the number of primes less than or equal to M. We use Sieve of Eratosthenes(http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) to do the same.

The time complexity of the first part of the problem is O(n) since we can calculate M using Dynamic Programming. The time complexity of the second part is O(n log log n). Hence, the overall time complexity for the problem becomes O(n log log n).

vector<int> sieve(int n)
{
    set<int> primes;
    vector<int> vec;

    primes.insert(2);

    for(int i=3; i<=n ; i+=2)
    {
        primes.insert(i);
    }       

    int p=*primes.begin();
    vec.push_back(p);
    primes.erase(p);

    int maxRoot = sqrt(*(primes.rbegin()));

    while(primes.size() > 0)
    {
        if(p > maxRoot)
        {
            while(primes.size() > 0)
            {
                p=*primes.begin();
                vec.push_back(p);
                primes.erase(p);        
            }
            break;
        }

        int i = p*p;  
        int temp = (*(primes.rbegin()));

        while(i<=temp)
        {
            primes.erase(i);
            i += p;
            i += p;
        }

        p=*primes.begin();
        vec.push_back(p);
        primes.erase(p);
    }

    return vec;
}

int main() 
{
    int t, N, M, P, i, count, res;
    vector<int> prime;
    vector<int>::iterator it;

    cin >> t;

    prime = sieve(217286);

    int a[41];
    for(i=0;i<4;i++)
        a[i] = 1;
    for(i=4;i<=40;i++)
        a[i] = a[i-1] + a[i-4];

    int numprime[41];
    for(i=0;i<41;i++)
    {
        count = 0;
        for(it=prime.begin();it!=prime.end();it++)
        {
            if(*it <= a[i])
                count++;
            else
                break;
        }    
        numprime[i] = count;
        count = 0;
    }

    while(t--)
    {
        cin >> N;
        res = numprime[N];
        cout << res << endl;
    }

    return 0;
}

https://codepair.hackerrank.com/paper/HzPdvtx6?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
   public Task() {
        numberOfWays = new int[MAXN];
        numberOfWays[0] = numberOfWays[1] = numberOfWays[2] = numberOfWays[3] = 1;
        for (int i = 4; i < numberOfWays.length; ++i) {
            numberOfWays[i] = numberOfWays[i - 1] + numberOfWays[i - 4];
        }

        isPrime = new boolean[numberOfWays[numberOfWays.length - 1]];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i < isPrime.length; ++i) {
            if (isPrime[i]) {
                for (int j = i * i; j < isPrime.length; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        primeList = new ArrayList<Integer>();
        for (int i = 2; i < isPrime.length; ++i) {
            if (isPrime[i]) {
                primeList.add(i);
            }
        }
    }

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.readInt();
        int m = numberOfWays[n];
        int res = Collections.binarySearch(primeList, m);
        if (res >= 0) {
            ++res;
        }
        else {
            res = -(res + 1);
        }
        out.println(res);
    }

https://github.com/havelessbemore/hackerrank/blob/master/algorithms/dynammic_programming/red-john-is-back.java