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}