Caching 1600 integers and searching from treeSet takes a lot of time

Question

What should I use to cache the result so that it takes less time to search? It currently takes a large number of minutes to complete 10000 test cases with range 1-99999999999999 (18 times 9 - the worst case), even though the search values have been hard-coded for testing purposes (1600, 1501).

Set<Integer> set = new TreeSet<Integer>();
//some logic to populate 1600 numbers
for (int cases = 0; cases < totalCases; cases++) {
    String[] str = br.readLine().split(" ");
    long startRange = Long.parseLong(str[0]);
    long endRange = Long.parseLong(str[1]);
    int luckyCount = 0;
    for (long num = startRange; num <= endRange; num++) {
        int[] longArray = { 1600, 1501 };
        if (set.contains(longArray[0]) && set.contains(longArray[1])) {
            luckyCount++;
        }

    }
    System.out.println(luckyCount);
}

It actually is a problem to find a lucky number - those numbers whose sum of digits and sum of square of digits are prime. I have implemented the Sieve of Eratosthenes for this. To optimize it further, I commented my getDigitSum method, and I thought was heavy, so I replaced it with two hard-coded values, but it still takes minutes to solve one test case. Here is a reference to actual problem asked.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Set;
import java.util.TreeSet;

public class Solution {

    private static int[] getDigitSum(long num) {

        long sum = 0;
        long squareSum = 0;
        for (long tempNum = num; tempNum > 0; tempNum = tempNum / 10) {
            if (tempNum < 0) {
                sum = sum + tempNum;
                squareSum = squareSum + (tempNum * tempNum);
            } else {
                long temp = tempNum % 10;
                sum = sum + temp;
                squareSum = squareSum + (temp * temp);

            }
        }
        int[] twosums = new int[2];
        twosums[0] = Integer.parseInt(sum+"");
        twosums[1] = Integer.parseInt(squareSum+"");
        // System.out.println("sum Of digits: " + twoDoubles[0]);
        // System.out.println("squareSum Of digits: " + twoDoubles[1]);
        return twosums;
    }

    public static Set<Integer> getPrimeSet(int maxValue) {
        boolean[] primeArray = new boolean[maxValue + 1];
        for (int i = 2; i < primeArray.length; i++) {
            primeArray[i] = true;
        }
        Set<Integer> primeSet = new TreeSet<Integer>();
        for (int i = 2; i < maxValue; i++) {
            if (primeArray[i]) {
                primeSet.add(i);
                markMutiplesAsComposite(primeArray, i);
            }
        }

        return primeSet;
    }

    public static void markMutiplesAsComposite(boolean[] primeArray, int value) {
        for (int i = 2; i*value < primeArray.length; i++) {
            primeArray[i * value] = false;

        }
    }

    public static void main(String args[]) throws NumberFormatException,
            IOException {
        // getDigitSum(80001001000l);
        //System.out.println(getPrimeSet(1600));
        Set set = getPrimeSet(1600);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int totalCases = Integer.parseInt(br.readLine());
        for (int cases = 0; cases < totalCases; cases++) {
            String[] str = br.readLine().split(" ");
            long startRange = Long.parseLong(str[0]);
            long endRange = Long.parseLong(str[1]);
            int luckyCount = 0;
            for (long num = startRange; num <= endRange; num++) {
                int[] longArray = getDigitSum(num);
                if(set.contains(longArray[0]) && set.contains(longArray[1])){
                    luckyCount++;
                }
            }
            System.out.println(luckyCount);
        }
    }
}

Answer 1

You claim the lookup in the TreeSet takes a long time, why don't you use a HashSet which guarantees constant time instead of the log(n) time of TreeSet.

Also did you profile your code to verify that it is the lookup that is taking so much time? And that it isn't something else?

Answer 2

There are few places in this implementation that can be improved. In order to to start attacking the issues i made few changes first to get an idea of the main problems: made the total start cases be the value 1 and set the range to be a billion (1,000,000,000) to have a large amount of iterations. also I use the method "getDigitSum" but commented out the code that actually makes the sum of digits to see how the rest runs: following are the methods that were modified for an initial test run:

private static int[] getDigitSum(long num) {

    long sum = 0;
    long squareSum = 0;
//    for (long tempNum = num; tempNum > 0; tempNum = tempNum / 10) {
//        if (tempNum < 0) {
//            sum = sum + tempNum;
//            squareSum = squareSum + (tempNum * tempNum);
//        } else {
//            long temp = tempNum % 10;
//            sum = sum + temp;
//            squareSum = squareSum + (temp * temp);
//
//        }
//    }
    int[] twosums = new int[2];
    twosums[0] = Integer.parseInt(sum+"");
    twosums[1] = Integer.parseInt(squareSum+"");
    // System.out.println("sum Of digits: " + twoDoubles[0]);
    // System.out.println("squareSum Of digits: " + twoDoubles[1]);
    return twosums;
}

and

public static void main(String args[]) throws NumberFormatException,
        IOException {
    // getDigitSum(80001001000l);
    //System.out.println(getPrimeSet(1600));
    Set set = getPrimeSet(1600);
    //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int totalCases = 1;
    for (int cases = 0; cases < totalCases; cases++) {
        //String[] str = br.readLine().split(" ");
        long startRange = Long.parseLong("1");
        long endRange = Long.parseLong("1000000000");
        int luckyCount = 0;
        for (long num = startRange; num <= endRange; num++) {
            int[] longArray = getDigitSum(num); //this method was commented for testing purpose and was replaced with any two hardcoded values
            if(set.contains(longArray[0]) && set.contains(longArray[1])){
                luckyCount++;
            }


        }
        System.out.println(luckyCount);
    }

} 

Running the code takes 5 minutes 8 seconds. now we can start optimizing it step by step. I will now mention the various points in the implementation that can be optimized.

1- in the method getDigitSum(long num)

int[] twosums = new int[2];
twosums[0] = Integer.parseInt(sum+"");
twosums[1] = Integer.parseInt(squareSum+"");

the above is not good. on every call to this method, two String objects are created , e.g. (sum+"") , before they are parsed into an int. considering the method is called billion times in my test, that produces two billion String object creation operations. since you know that the value is an int (according to the math in there and based on the links you provided), it would be enough to use casting:

twosums[0] = (int)sum;
twosums[1] = (int)squareSum;

2- In the "Main" method, you have the following

for (long num = startRange; num <= endRange; num++) {
            int[] longArray = getDigitSum(num); \\this method was commented for testing purpose and was replaced with any two hardcoded values
            if(set.contains(longArray[0]) && set.contains(longArray[1])){
                luckyCount++;
            }
   }

here there are few issues:

a- set.contains(longArray[0]) will create an Integer object (with autoboxing) because contains method requires an object. this is a big waste and is not necessary. in our example, billion Integer objects will be created. Also, usage of set, whether it is a treeset or hash set is not the best for our case.

what you are trying to do is to get a set that contains the prime numbers in the range 1 .. 1600. this way, to check if a number in the range is prime, you check if it is contained in the set. This is not good as there are billions of calls to the set contains method. instead, your boolean array that you made when filling the set can be used: to find if the number 1500 is prime, simply access the index 1500 in the array. this is much faster solution. since its only 1600 elements (1600 is greater than max sum of sqaures of digits of your worst case), the wasted memory for the false locations is not an issue compared to the gain in speed.

b- int[] longArray = getDigitSum(num); an int array is being allocated and returned. that will happen billion times. in our case, we can define it once outside the loop and send it to the method where it gets filled. on billion iterations, this saved 7 seconds, not a big change by itslef. but if the test cases are repeated 1000 times as you plan, that is 7000 second.

therefore, after modifying the code to implement all of the above, here is what you will have:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Set;
import java.util.TreeSet;

public class Solution {

private static void getDigitSum(long num,int[] arr) {

    long sum = 0;
    long squareSum = 0;
//    for (long tempNum = num; tempNum > 0; tempNum = tempNum / 10) {
//        if (tempNum < 0) {
//            sum = sum + tempNum;
//            squareSum = squareSum + (tempNum * tempNum);
//        } else {
//            long temp = tempNum % 10;
//            sum = sum + temp;
//            squareSum = squareSum + (temp * temp);
//
//        }
//    }
    arr[0] = (int)sum;
    arr[1] = (int)squareSum;
    // System.out.println("sum Of digits: " + twoDoubles[0]);
    // System.out.println("squareSum Of digits: " + twoDoubles[1]);

}

public static boolean[] getPrimeSet(int maxValue) {
    boolean[] primeArray = new boolean[maxValue + 1];
    for (int i = 2; i < primeArray.length; i++) {
        primeArray[i] = true;
    }

    for (int i = 2; i < maxValue; i++) {
        if (primeArray[i]) {
            markMutiplesAsComposite(primeArray, i);
        }
    }

    return primeArray;
}

public static void markMutiplesAsComposite(boolean[] primeArray, int value) {
    for (int i = 2; i*value < primeArray.length; i++) {
        primeArray[i * value] = false;

    }
}

public static void main(String args[]) throws NumberFormatException,
        IOException {
    // getDigitSum(80001001000l);
    //System.out.println(getPrimeSet(1600));
    boolean[] primeArray = getPrimeSet(1600);
    //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int totalCases = 1;
    for (int cases = 0; cases < totalCases; cases++) {
        //String[] str = br.readLine().split(" ");
        long startRange = Long.parseLong("1");
        long endRange = Long.parseLong("1000000000");
        int luckyCount = 0;
        int[] longArray=new int[2];
        for (long num = startRange; num <= endRange; num++) {
            getDigitSum(num,longArray); //this method was commented for testing purpose and was replaced with any two hardcoded values
            if(primeArray[longArray[0]] && primeArray[longArray[1]]){
                luckyCount++;
            }


        }
        System.out.println(luckyCount);
    }

}
}

Running the code takes 4 seconds.

the billion iterations cost 4 seconds instead of 5 minutes 8 seconds, that is an improvement. the only issue left is the actual calculation of the sum of digits and sum of squares of digits. that code i commented out (as you can see in the code i posted). if you uncomment it, the runtime will take 6-7 minutes. and here, there is nothing to improve except if you find some mathematical way to have incremental calculation based on previous results.

Answer 3

If I'm right the following is the same:

final Set<Integer> set = new TreeSet<Integer>();
//some logic to populate 1600 numbers
for (int cases = 0; cases < totalCases; cases++) {
    final String[] str = br.readLine().split(" ");
    final long startRange = Long.parseLong(str[0]);
    final long endRange = Long.parseLong(str[1]);
    int luckyCount = 0;
    final int[] longArray = { 1600, 1501 };
    if (set.contains(longArray[0]) && set.contains(longArray[1])) {
        luckyCount += (endRange - startRange + 1);
    }
    System.out.println(luckyCount);
}

It eliminates an unnecessary loop.