# HackerRank Red John is Back problem solution

In this 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 4x1 and 1x4 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 the bricks can be arranged to cover the entire wall.

## Problem solution in Python.

```def primes(n):
""" Returns  a list of primes < n """
if n <= 2: return 0
sieve = [True] * n
for i in range(3,int(n**0.5)+1,2):
if sieve[i]:
sieve[i*i::2*i]=[False]*int((n-i*i-1)/(2*i)+1)
return len([i for i in range(3,n,2) if sieve[i]]) + 1

def find_configs(N):
if N == 0:
return 1
elif N < 0:
return 0

return find_configs(N-1) + find_configs(N-4)

T = int(input())
for i in range(T):
print(primes(find_configs(int(input()))+1))```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
int ar[]=new int[41];
ar[1]=1;
ar[2]=1;
ar[3]=1;
ar[4]=2;
for(int i=5;i<=40;i++) {
ar[i]=ar[i-4]+ar[i-1];
}
int x=ar[40];
boolean prime[]=new boolean[(int)x+1];
for(int i=2;i<=x;i++) {
prime[i]=true;
}
for(int i=2;i<=Math.sqrt(x+1);i++) {
if(prime[i]) {
for(int j=i*i;j<=x;j+=i) {
prime[j]=false;
}
}
}
int cnt[]=new int[(int)(x+1l)];
for(int i=2;i<=x;i++)
{
if(prime[i])
cnt[i]=1;
cnt[i]+=cnt[i-1];
}
while(T-->0) {
int n=sc.nextInt();
System.out.println(cnt[ar[n]]);
}
}
}```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <stdio.h>
#include <iostream>
#define MAXN 250000
using namespace std;

int n, ways, ans;

int isPrime[MAXN];

void preProcess()
{

for(int i = 0; i <= MAXN; i++)
isPrime[i] = 1;

isPrime[1] = isPrime[0] = 0;
for(int i = 2; i * i <= MAXN; i++)
if(isPrime[i])
for(int k = i * i; k <= MAXN; k += i)
isPrime[k] = 0;
}

int solve(int n1)
{
if(n1 < 0) return 0;
else if(n1 <= 3) return 1;
else return solve(n1 - 1) + solve(n1 - 4);
}

int main()
{
int t;

scanf("%d", &t);
preProcess();
while(t--)
{
scanf("%d", &n);
ways = solve(n);
ans = 0;
for(int i = 2; i <= ways; ++i)
if(isPrime[i]) ++ans;

printf("%d\n", ans);
}

return 0;
}```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int arr[50];
int func(int n){
if(n == 0)
return 1;
else if(n == 1)
return 1;
else if(n == 2)
return 1;
else if(n == 3)
return 1;
else{
if(arr[n]!=0)
return arr[n];
int temp = func(n-1) + func(n-4);
arr[n] = temp;
return temp;
}
}
int main(){
int sieve[1000000] = {0};
int i;
for(i=2;i<1000000;i++){
int t = i;
while(1){
if(t>1000000)
break;
t += i;
sieve[t] = 1;
}
}
int count[1000000] = {0};
int num = 0;
for(i=2;i<1000000;i++){
if(sieve[i]==0)
num++;
count[i] = num;
}
for(i=0;i<50;i++)
arr[i] = 0;
int n;
int test;
scanf("%d",&test);
for(i=0;i<test;i++){
scanf("%d",&n);
printf("%d\n",count[func(n)]);
}
return 0;
}```

{"mode":"full","isActive":false}