package hackerrank;

import java.util.Scanner;

/**
 * https://www.hackerrank.com/challenges/red-john-is-back
 */
public class RedJohnIsBack {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // TODO
    }
}

@@ -14,16 +14,64 @@
 rrank;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A
 import j
@@ -193,108 +193,1231 @@
    p
-ublic static void main(String%5B%5D args) %7B%0A        Scanner in = new Scanner(System.in);%0A        // TODO
+rivate static int redJohnIsBack(int n) %7B%0A        int x = redJohnIsBack(n, new HashMap%3C%3E());%0A        return primes(x);%0A    %7D%0A%0A    private static int primes(int n) %7B%0A        boolean%5B%5D primes = new boolean%5Bn + 1%5D;%0A        int count = 0;%0A        for (int i = 2; i %3C= n; i++) %7B%0A            if (primes%5Bi%5D) %7B%0A                continue;%0A            %7D%0A            count++;%0A            int j = i;%0A            while (j %3C= n) %7B%0A                primes%5Bj%5D = true;%0A                j += i;%0A            %7D%0A        %7D%0A        return count;%0A    %7D%0A%0A    private static int redJohnIsBack(int n, Map%3CInteger, Integer%3E memo) %7B%0A        if (n %3C 0) %7B%0A            return 0;%0A        %7D%0A        if (n == 0) %7B%0A            return 1;%0A        %7D%0A        if (memo.containsKey(n)) %7B%0A            return memo.get(n);%0A        %7D%0A        int a = redJohnIsBack(n - 1, memo);%0A        int b = redJohnIsBack(n - 4, memo);%0A        int total = a + b;%0A        memo.put(n, total);%0A        return total;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Scanner in = new Scanner(System.in);%0A        int testCases = in.nextInt();%0A        for (int t = 0; t %3C testCases; t++) %7B%0A            int n = in.nextInt();%0A            System.out.println(redJohnIsBack(n));%0A        %7D
 %0A   

Solve Red John Is Back