HackerRank Red John is Back Problem Solution

In this post, we will solve HackerRank Red John is Back Problem Solution.

Red John has committed another murder. This time, he doesn’t leave a red smiley behind. Instead he leaves 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 has an infinite supply of bricks of size 4×1 and 1×4 in her house. There is a hidden safe which can only be opened by a particular configuration of bricks. First we must calculate the total number of ways in which the bricks can be arranged so that the entire wall is covered. The following diagram shows how bricks might be arranged to cover walls where 1 < n < 4:

There is one more step to the puzzle. Call the number of possible arrangements M. Patrick
must calculate the number of prime numbers P in the inclusive range 0 – M. As an example, assume n = 3. From the diagram above, we determine that there is only one configuration that will cover the wall properly. 1 is not a prime number, so P = 0. A more complex example is n = 5. The bricks can be oriented in 3 total configurations that cover the wall. The two primes 2 and 3 are less than or equal to 3, so P = 2.

Function Description

Complete the redJohn function in the editor below. It should return the number of primes determined, as an integer.

redJohn has the following parameter(s):

n: an integer that denotes the length of the wall

Input Format

The first line contains the integer t, the number of test cases. Each of the next t lines contains an integer n, the length of the 4 x n wall.

Sample Input

2
1
7

Sample Output

0
3

HackerRank Red John is Back Problem Solution

Red John is Back C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int a[1000000]={0},f[100000],l;

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int t,n,i,sum,j,k,s;
    sieve();
    scanf("%d",&t);
    while(t--)
        {
        scanf("%d",&n);
        sum=0;
        i=n/4;
        while(i)
            {
            j=i;
            k=n-3*i;
            s=1;
            while(j--)
                {
                s*=k;
                k--;
            }
            
            
            sum+=(s/fact(i));
            i--;
        }
        if(n)
            sum++;
        
        printf("%d\n",sum<2?0:prime(sum));
    }
    return 0;
}

int fact(int n)
    {
    int f=1;
    while(n)
        {
        f*=n;
        n--;
    }
return f;
}

sieve()
{
int i,j;
for(i=2;i<1000000;i++)
{
if(a[i]!=1)
{
for(j=i*2;j<1000000;j=j+i)
a[j]=1;
f[l++]=i;
}
}
}

int prime(int n)
    {
    int i;
    for(i=0;i<100000;i++)
        {
        if(n==f[i])
            {
            i++;
            break;
        }
        else if(n<f[i])
            break;
        }
    return i;
    }

Red John is Back C++ Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> v;
int prime[312345];
int f(int n){
    if(n==0) return 1;
    if(n<0) return 0;
    return f(n-1)+f(n-4);
}

void seive(int n){
    for(int i=0;i<=n;i++){
        prime[i] = 1;
    }
    prime[0] = 0;
    prime[1] = 0;
    for(int i=2;i<=sqrt(n);i++){
        if(prime[i]){
            for(int j=2;i*j<=n;j++){
                prime[i*j] = 0;
            }
        }
    }
    for(int i=0;i<=n;i++){
        if(prime[i]) v.push_back(i);
    }
}


int main() {
    seive(312345);
    int tests;
    cin >> tests;
    while(tests--){
        int n;
        cin >> n;
        cout << upper_bound(v.begin(),v.end(),f(n)) - v.begin() << endl;
    }

}

Red John is Back C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        int size = int.Parse(Console.ReadLine());
        int[] N = new int[size];
        int[] cfs = new int[size];
        int i;
        bool[] primes;
        
        for (i=1; i<=size; i++)
            {
                N[i-1] = int.Parse(Console.ReadLine());
                cfs[i-1] = configurations(N[i-1]/4,N[i-1]%4);
        }
        
        primes = MakeSieve(cfs.Max());
        
        for (i=0;i<size;i++)
            {
                Console.WriteLine(countPrimes(primes,cfs[i]));
            
        }
        
        
    }
    
    static int configurations(int d, int r)
        {
            if (d == 0)
            { return 1; }
            else
            { return configs(d, r) + configurations(d - 1, r + 4); }
        
        }
    
    static int countPrimes(bool[] ps, int n)
        {
        int i;
        int total = 0;
           for (i=1; i<=n; i++)
               {
               if (ps[i])
                   {total++;}
        
           }
        return total;        
    }
    
    static int factorial(int n)
    {
        if (n == 1)
        { return 1; }
        else
        { return n * factorial(n - 1); }
    }
    
    static int configs(int d, int r)
        {
            int i;
            int rtnval = d + r;
            for (i = d + r-1; i > r; i--)
            {
                rtnval = rtnval * i;
            }

            return rtnval / factorial(d);
    }
    
    static public bool[] MakeSieve(int max)
{
    // Make an array indicating whether numbers are prime.
    bool[] is_prime = new bool[max + 1];
    for (int i = 2; i <= max; i++) is_prime[i] = true;

    // Cross out multiples.
    for (int i = 2; i <= max; i++)
    {
        // See if i is prime.
        if (is_prime[i])
        {
            // Knock out multiples of i.
            for (int j = i * 2; j <= max; j += i)
                is_prime[j] = false;
        }
    }
        
    return is_prime;
}
}

Red John is Back Java Solution

import java.util.Arrays;
import java.util.Scanner;

public class Solution 
{
    private Scanner in;
    
    
    public Solution()
    {
        in = new Scanner(System.in);
        
    }
    
    public void run()
    {
        int testCases = in.nextInt();
        for(int test=0; test<testCases; test++)
        {
            int n = in.nextInt();
            if(n < 4)
            {
                System.out.println(0);
                continue;
            }
            // solve if n >= 4
            int[] dp = new int[n+1];
            dp[0] = 0;
            dp[1] = 1;
            dp[2] = 1;
            dp[3] = 1;
            dp[4] = 2;
            func(dp, n);
            System.out.println(primesCount(dp[n]));
        }
    }
    
    public int primesCount(int n)
    {
        if(n<2)
            return 0;
        boolean[] prime = new boolean[n+1];
        Arrays.fill(prime, true);
        prime[0] = false; // mark 0 as non - prime number
        prime[1] = false; // mark 1 ass non- prime number
        // logic is any starting true marked boolean is prime 2 3 5 so on
        int count = 0; // count the number of prime till n;
        for(int i=2; i<=n; i++)
        {
            if(prime[i])
            {
                count++;
                for(int j=2; j<=n/i; j++)
                    prime[j*i] = false;
            }
        }
        return count;
        
            
    }
    // function to find the number of bricks required using dynamic programming
    public int func(int[] dp, int n)
    {
        if(dp[n] > 0)
            return dp[n];
        
        dp[n] = func(dp, n-1) + ((n>3)?func(dp,n-4):0);
        return dp[n];
    }
    
    public static void main(String[] args)
    {
        Solution solution = new Solution();
        solution.run();
    }
}

Red John is Back JavaScript Solution

function processData(input) {
    //Enter your code here
    var arr = input.split("\n");
    var remainingBricks = 0;
    var totalCombination = 0
    var totalNumOfArrangements = 0;
    var totalNumOfSquares = 10;
    for(var squares = 0; squares <= totalNumOfSquares; squares++)
    {
        remainingBricks = 40 - squares * 4;
        totalCombination += C(remainingBricks + squares, squares);
    }
    var primes = [];
    for(var i = 2; i <= totalCombination; i++) {
        primes[i] = true;
    }
    var limit = Math.sqrt(totalCombination);
    for(var i = 2; i <= limit; i++) {
        if(primes[i] === true) {
            for(var j = i * i; j <= totalCombination; j += i) {
                primes[j] = false;
            }
        }
    }
    for(var i=1;i<=arr[0];i++){
        totalNumOfArrangements = 0;
        totalNumOfSquares = arr[i] / 4;
        for(var squares = 0; squares <= totalNumOfSquares; squares++)
        {
            remainingBricks = arr[i] - squares * 4;
            totalNumOfArrangements += C(remainingBricks + squares, squares);
        }
        var total = 0;
        if(arr[i]>=4){
            for(var j = 2; j <= totalNumOfArrangements; j++) {
                if(primes[j] === true){
                    total++;
                }
            }
        }
        process.stdout.write(total+"\n");
    }
}

function factorial(num)
{
    // If the number is less than 0, reject it.
    if (num < 0) {
        return -1;
    }
    // If the number is 0, its factorial is 1.
    else if (num == 0) {
        return 1;
    }
    // Otherwise, call this recursive procedure again.
    else {
        return (num * factorial(num - 1));
    }
}



function C(num1,num2){
    return factorial(num1)/(factorial(num2)*factorial(num1-num2));
}



process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Red John is Back Python Solution

T = int(input())
for t in range(T):
	m = int(input())
	a = [0] * max(m+1, 4)
	a[0] = a[1] = a[2] = a[3] = 1
	for i in range(4, m+1):
		a[i] = a[i - 1] + a[i - 4]

	maxPrime = a[m]
	isPrime = [True] * (maxPrime + 1)
	for i in range(2, maxPrime + 1):
		curr = 2 * i
		while curr <= maxPrime:
			isPrime[curr] = False
			curr += i
	nbPrimes = 0
	for i in range(2, maxPrime + 1):
		if isPrime[i]:
			nbPrimes += 1
	print(nbPrimes)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python