4
\$\begingroup\$

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;
    }
}
\$\endgroup\$
3
\$\begingroup\$

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);
\$\endgroup\$
0
\$\begingroup\$
  • 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.

\$\endgroup\$
5
  • \$\begingroup\$ 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? \$\endgroup\$
    – SirPython
    Jul 21 '15 at 0:09
  • \$\begingroup\$ @SirPython Better now? (This deserved a downvote and a deletion request? Really?) \$\endgroup\$ Jul 21 '15 at 0:14
  • \$\begingroup\$ Yes, this is much better. And, yes, it did deserve a downvote; it was an answer of extremely poor quality. \$\endgroup\$
    – SirPython
    Jul 21 '15 at 0:16
  • \$\begingroup\$ @SirPython Extremly poor? You're quite stern. I think it was obvious to any decent Java developer. You're not one, are you? \$\endgroup\$ Jul 21 '15 at 0:24
  • \$\begingroup\$ 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. \$\endgroup\$
    – SirPython
    Jul 21 '15 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.