Avoiding traps

There is a cave of $N$ cells where each cell has a trap or is safe to land. From a cell $i$, you can jump to cells $i+1$ or $i+2$. Also, if number $i$ is special, then you can also jump from cell $i$ to cell $i+A$ where $A=numberofprimesin[1,i]$. A number $i$ can be special if $\frac{A}{i}\ge \frac{r1}{r2}$.

You are given the following:

• Some arbitrary numbers $r_1$ and  $r_2$
• The number of cells $N$ in the cave where each cell contains either '#' or '*'
• Details of the cave

Example:

Input : 
1 2
8
########
Output:
3

Approach

Java

import java.util.Arrays;

public class AvoidingTraps {
    public static void main(String[] args) {
        primeCalculation();
        int r1 = 1;
        int r2 = 2;
        int N = 8;
        String s = "########";
        String res = avoidingTrap(r1, r2, N, s);
        System.out.println(res);

    }

    static final int MAX = Integer.MAX_VALUE;
    static final int MAX_N = 100000;
    static double FACTOR;

    static boolean[] nonPrimes;
    static int[] countPrimes;

    static void primeCalculation() {
        nonPrimes = new boolean[MAX_N + 1];
        countPrimes = new int[MAX_N + 1];
        nonPrimes[0] = nonPrimes[1] = true;

        for (int i = 2; i <= MAX_N; i++) {
            if (!nonPrimes[i]) {
                // cumCountPrimes++;
                for (int j = i + i; j <= MAX_N; j += i) {
                    nonPrimes[j] = true;
                }
            }
        }
        for (int i = 1; i <= MAX_N; i++)
            if (!nonPrimes[i])
                countPrimes[i] = 1 + countPrimes[i - 1];
            else
                countPrimes[i] = countPrimes[i - 1];

    }

    static String avoidingTrap(int r1, int r2, int n, String s) {
        FACTOR = (double) (r1) / r2;

        char[] cells = s.toCharArray();
        if ((n > 2 && cells[1] == '*' && cells[2] == '*') || cells[n - 1] == '*' || cells[0] == '*')
            return "No way!";
        int[] minSteps = new int[n];
        Arrays.fill(minSteps, MAX);

        minSteps[0] = 0;

        for (int i = 0; i < n - 1; i++) {
            if (minSteps[i] != MAX) {
                if (cells[i + 1] == '#')
                    minSteps[i + 1] = Math.min(minSteps[i + 1], 1 + minSteps[i]);
                if (i + 2 < n && cells[i + 2] == '#')
                    minSteps[i + 2] = Math.min(minSteps[i + 2], 1 + minSteps[i]);
                if (isSpecial(i + 1)) {
                    int A = countPrimes[i + 1];
                    if (i + A < n && cells[i + A] == '#') {
                        minSteps[i + A] = Math.min(minSteps[i + A], 1 + minSteps[i]);
                    }
                }
            }
        }
        if (minSteps[n - 1] == MAX)
            return "No way!";
        else
            return Integer.toString(minSteps[n - 1]);
    }

    static boolean isSpecial(int i) {
        int A = countPrimes[i];
        double lhs = (double) (A) / i;
        return lhs >= FACTOR;
    }
}