# Find the highest occurring digit in the prime numbers present between L and R (both inclusive)

Given two numbers L and R, find the highest occurring digit in the prime numbers present between L and R (both inclusive). If multiple digits have the same highest frequency print the largest of them. If there are no prime no.s between L and R, print -1.

How can I optimize this code further in terms of running time?

package com;

import java.util.Arrays;

/**
* Created by ankur on 19/7/15.
*/
public class HighestOccuringDigit {
private static int MAX = 1000000;
private static boolean[] isPrime = generatePrime();
public static void main(String...strings){

int index = getMaxOccuredDigit(13,13);
if (index != 0){
System.out.println(index);
}else{
System.out.println(-1);
}
}

private static int getMaxOccuredDigit(int lower, int higher){
int[] highestDigitCount = new int[10];
int max = 0;
int maxIndex = 0;
if (lower < 3){
highestDigitCount[2] = 1;
lower = 3;
}
for (int i = lower; i <= higher; i++){
//System.out.println(i);
int index = (i - 3) >> 1;
//System.out.println(i);
if (((i & 1) != 0)   && isPrime[index]){
//System.out.println(i);
int[] digitsCount = getDigitCount(i);
for (int j = 0; j < 10; j++){
highestDigitCount[j] = highestDigitCount[j] + digitsCount[j];
if (highestDigitCount[j] > max){
max = highestDigitCount[j];
}
}
}
}
if (max == 0){
return 0;
}
for(int i = 0; i < 10; i++){
if (highestDigitCount[i] == max){
maxIndex =  i;
}
}
return maxIndex;
}

private static int[] getDigitCount(int prime){
int[] digitsCount = new int[10];
Arrays.fill(digitsCount, 0);
while(prime != 0){
int lastDigit = prime % 10;
digitsCount[lastDigit] += 1;
prime /= 10;
}

return digitsCount;
}

private static boolean[] generatePrime(){
int root = (int) Math.sqrt(MAX) + 1;
root = (root >> 1) - 1;
int limit = (int) ((MAX - 1) >> 1);
boolean[] isPrime = new boolean[limit];
Arrays.fill(isPrime, true);
for( int i = 0; i< root; i++){
if(isPrime[i]){
for(int j = ((i * (i + 3) << 1) + 3), p = (i << 1) + 3; j < limit; j += p){
isPrime[j] = false;
}
}
}
return isPrime;
}
}


In the code:

if (index != 0){
System.out.println(index);
}else{
System.out.println(-1);
}


Using a ternary reduces clutter and improves readibility:

System.out.println(index == 0 ? -1 : index);

• In this:

int limit = (int) ((MAX - 1) >> 1);


the cast isn't necessary since MAX is an int. The parentheses aren't necessary due to the operator precedence:

int limit = MAX - 1 >> 1;

• I'd write the for expressions on multiple lines and remove one pair of parentheses for better readability:

for (int j = (i * (i + 3) << 1) + 3,
p = (i << 1) + 3;
j < limit; j += p)

• I'd let while, if, for follow by a space to distinguish it from method invocations (as you do it at the beginning). I'd also surround else with spaces.

• I'd write:

for (int j = 0; j <= 9; j++)


rather than:

for (int j = 0; j < 10; j++)


Such reflecting the range of decimal digits.

• Please add some more explanation to your post. Why is the cast unnecessary? Why are the parentheses unnecessary? Why is the solution you presented better than the OP's? Jul 21 '15 at 0:09
• @SirPython Better now? (This deserved a downvote and a deletion request? Really?) Jul 21 '15 at 0:14
• Yes, this is much better. And, yes, it did deserve a downvote; it was an answer of extremely poor quality. Jul 21 '15 at 0:16
• @SirPython Extremly poor? You're quite stern. I think it was obvious to any decent Java developer. You're not one, are you? Jul 21 '15 at 0:24
• Yes, I am a Java developer. I'm sorry if my statement came up as harsh. In this site, we like strong answers with recommendations and evidence/support for these recommendations. However, your old post did not have any of these. As such, you post came up as in the "Low Quality Posts" section of this site's review area. Jul 21 '15 at 0:26