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.

hackerrank red john is back problem solution


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}