Calculating the number of prime numbers to solve the puzzle

Question

How can the following program execution time improved? I have used dynamic programming in both "recursive" as well as "prime" function, but I'm not getting the efficient execution time.

There is a wall of size 4xN in the victim's house where. The victim also has an infinite supply of bricks of size 4x1 and 1x4 in her house. In every configuration, the wall has to be completely covered using the bricks. Gale Bertram wants to know the total number of ways in which the bricks can be arranged on the wall so that a new configuration arises every time.

Let the number of Configuration = \$M\$.

So, he wants Patrick to calculate the number of prime numbers (say \$P\$) up to \$M\$ (i.e. \$<= M\$). You are required to help Patrick correctly solve the puzzle.

Sample Input

The first line of input will contain an integer \$T\$ followed by \$T\$ lines each containing an integer \$N\$.

Sample Output

Print exactly one line of output for each test case. The output should contain the number \$P\$.

Constraints

\$1 <= T <= 20\$
\$1 <= N <= 40\$

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class Solution{
    public static int[] b = new int[217287];
    public static void main(String[] args){
        Scanner stdin = new Scanner(System.in);
        int t = stdin.nextInt();
        int[] a = new int[41]; //array initialized before because the value remains same.
        for(int j=0;j<4;j++){
                a[j] = 1;          //till n<=3, number of possiblities = 1. These will work as base cases.
            }
            a[4] = 2;
        for(int x=0;x<t;x++){
            int n = stdin.nextInt();
            for(int i=5;i<=n;i++){
                a[i] = -1;         //initialise all value in the array as -1.
            }
            if(n<4)
                System.out.println("0"); // if n<4, number of possibilities =1. So no prime number before that is 0.
            else{
                         //for n=4, possibilities = 2. This is a base case.
            int num1 = recursive(a,n);          // storing number of possibilities in num1.
            int num2 = prime(num1);    //calling to calculate number of prime numbers before or equal to num1.
            System.out.println(num2);
            }
        }
    }
    public static int recursive(int[] a, int n){
        if(a[n]!=-1)                             // retrieving a[n] value if already calculated.
            return a[n];
        else{
            a[n] = recursive(a,n-1) + recursive(a,n-4); // calling recursively.If we fill with a 4*1 first tile then number 
                                                        //tiles left is n-1(try visualising).If we fill 1*4 tile first
                                                        // we have n-4 tile left.
            return a[n];
        }
    }
    public static int prime(int n){
        int count = 0;
        if(b[n]!=0)
            return b[n];
        else{
        for(int i=2;i<=n;i++){
            if(b[i]!=0){
                count = b[i];
            }
            else{
            int flag = 0;           
            for(int j=2;j<=i/2;j++){
                if(i%j==0){
                    flag = 1;
                    break;
                    }
                }
        if(flag==0){
            count++;
            b[i]=count;
        }
        }
        }
        return count;
        }
    }
}

I got a timeout (more than 4s) for the following input:

20
35
23
25
38
4
35
19
8
23
35
3
36
12
10
30
13
18
31
40
37

Answer 1

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;

Clean up those imports. Importing everything in a package is a bad idea, as it might easily lead to conflicts between same named classes. Also it is hard to see what is actually used.

---

You ain't got a package defined, define one.

---

class Solution{

That's a not very good class name. Classes should be named after what purpose they serve, or what purpose the methods contained within the class serve.

---

public static int[] b = new int[217287];

Here is the ultimate rule for variable naming:

You're only entitled to use one character variable names if you're dealing with dimensions (x, y, z). Second best is you're allowed to use one character variable names in simple for loops (i, j, k)...but the last point is up for debate and it should not be the case.

And here is a simple guide for naming variables:

Name variables after what they contain. You're not allowed to use one character variables except when dealing with dimensions.

Why is it so important to name variables after what they do? Well, quick, tell me what this code does: if (b[n] != 0).

---

for(int x=0;x<t;x++){

This is even worse. x is normally only used for the dimension, so unless you're looping over the x dimension of something here, this variable should be called different and according to what it does.

---

for(int i=0;i<=n;i++){
    a[i] = -1;         //initialise all value in the array as -1.
}

Only comment things that are not obvious from the code. In this case I can see that the array is initialized to -1...or I could see it if the variables would have fitting names:

for (int index = 0; index < a.length; index++) {
    a[index] = -1;
}

Note that a is still not a good name. Also what I do not see from the code at this point is why it is initialized to that value. So if to comment something, then the why is interesting.

---

if(n<4)
    System.out.println("0"); // if n<4, number of possibilities =1. So no prime number before that is 0.
else{

You should not omit braces from ifs and fors, even one line once. It can be very confusing in the long run.

---

else{
for(int j=0;j<4;j++){
    a[j] = 1;          //till n<=3, number of possiblities = 1. These will work as base cases.
}
a[4] = 2;             //for n=4, possibilities = 2. This is a base case.
int num1 = recursive(a,n);          // storing number of possibilities in num1.
int num2 = prime(num1);    //calling to calculate number of prime numbers before or equal to num1.
System.out.println(num2);
}

Why are your else branches not indented?

---

public static int recursive(int[] a, int n){

That's another not very good name. Functions should be verbs, not adjectives. They have a function, not a state, and the name should mirror that function.

---

You have no JavaDoc in there, fix that.

---

Consider using a code formatter, and then consider using more blank lines and more whitespace to make the code easier readable.

Answer 2

First off, fix your indentation near single line if statements that have else statements. They're making your code hard to read and I even made a mistake interpretting the bottom most function (I thought it would return after a single iteration, went to go to great lengths to explain that's not how things would work and that it was broken, when during fixing the formatting, I found out it actually worked differently.)

And there's enter code here stuck in there... I assume it doesn't belong there.

Still. Let's take a look at your top most for loop:

        int n = stdin.nextInt();
        int[] a = new int[n+1];`enter code here`
        for(int i=0;i<=n;i++){
            a[i] = -1;         //initialise all value in the array as -1.
        }
        if(n<4)
            System.out.println("0"); // if n<4, number of possibilities =1. So no prime number before that is 0.
        else{
        for(int j=0;j<4;j++){
            a[j] = 1;          //till n<=3, number of possiblities = 1. These will work as base cases.
        }
        a[4] = 2;             //for n=4, possibilities = 2. This is a base case.
        int num1 = recursive(a,n);          // storing number of possibilities in num1.
        int num2 = prime(num1);    //calling to calculate number of prime numbers before or equal to num1.
        System.out.println(num2);
        }

Since it's a performance issue, one improvement I would have is to reshuffle the order of operations.

What you do is...

read int
declare array
set values in array
if(n<4){
    print 0
} else {
    stuff
}

That's just a waste. Let's do this instead:

read int
if(n<4){
    print 0
    continue
}
declare array
set values in array
stuff

Now, lets look at what I defined as "stuff".

        for(int j=0;j<4;j++){
            a[j] = 1;          //till n<=3, number of possiblities = 1. These will work as base cases.
        }
        a[4] = 2;             //for n=4, possibilities = 2. This is a base case.
        int num1 = recursive(a,n);          // storing number of possibilities in num1.
        int num2 = prime(num1);    //calling to calculate number of prime numbers before or equal to num1.
        System.out.println(num2);

It does...

set array index 0-3 to 1
set array index 4 to 2
calculate recursive
calculate prime
print prime

You could remove the local stores here. You don't need those. More importantly though, when we combine the two...

read int
if(n<4){
    print 0
    continue
}
declare array
set values in array
set array index 0-3 to 1
set array index 4 to 2
calculate recursive
calculate prime
print prime

We're writing double! Let's not.

read int
if(n<4){
    print 0
    continue
}
declare array
set array index 0-3 to 1
set array index 4 to 2
set values in array, from index 5 to and including index n to -1
calculate recursive
calculate prime
print prime

Or, in code...

        int n = stdin.nextInt();
        if(n < 4){
            System.out.println("0"); // if n<4, number of possibilities =1. So no prime number before that is 0.
            continue;
        }
        int[] a = new int[n+1];
        for(int j=0;j<4;j++){
            a[j] = 1;          //till n<=3, number of possiblities = 1. These will work as base cases.
        }
        a[4] = 2;
        for(int i=5;i<=n;i++){
            a[i] = -1;         //initialise all remaining value in the array as -1.
        }
        System.out.println(prime(recursive(a,n)));

Note that this is just me looking at performance, and not readability, or even logic. It might even be the case that the JVM is just as smart as me and does all of this for you. Additionally, you might get more of a speed up by looking at the more inner loops.