Finding numbers whose product of the digits are perfect squares

How can I decrease the running time and compile time of the following code?


Given three integers A, B and K, you need to report the Kth number
between A and B (both inclusive), satisfying the property that: the
number does not contain a digit 'zero' and product of digits of number
is a perfect square. If there doesn't exist that Kth number output
"-1"(without quotes).


Input:


First Line contains the number of test cases \$T\$. Next \$T\$ lines contain 3
space separated integers A, B, K as mentioned in the task.


Output:


Output \$T\$ lines as answer for every test case.


Constraints:


\$1 ≤ T ≤ 100\$

\$1 ≤ A ≤ B ≤ 10^{18}\$

\$1 ≤ K ≤ 10^7\$


Sample input:

3 
1 10 4
8 14 2
1 1000 23

Output:

-1
11
119

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int cases = in.nextInt();
    long A,B,K;

    int caseNum =0;
    while(caseNum  products = new ArrayList<>();
        long product = 1;
        for(long i=A,k=0;i temp = new ArrayList<>();
            while(num>0)
            {
                temp.add(num%10);
                num = num/10;
            }
            for(int j=0;j<temp.size();j++)
            {
                if(temp.get(j)==0){
                    product=-1;
                    break;

                }
                product = product*temp.get(j);
                //System.out.println("Currently processing: "+ temp.get(j));

            }
            sqrt = Math.sqrt(product);

            if( product%sqrt==0)
            {   products.add(i);

            }
            product=1;  
        }
        try{
            System.out.println(products.get((int)K-1));
        }catch (Exception e) {
            // TODO: handle exception
            System.out.println(-1);
        }

        caseNum++;
    }
}
}

Compile time really shouldn't be an issue. Right now, I would focus on readability, and then maybe runtime performance.

Variable names

Normally, I really dislike short variable names. In this case it's ok for A, B, and K, because they are part of the question. But if you do use the same variable names as in the question, you should probably do it consistently: cases should be T.

For the other variable names, you have no excuses: temp isn't a good name, and caseNum vs cases is also somewhat confusing. The worst is probably k, as you already have K.

Perform Action on Number

Instead of num = num/10; you can write num /= 10, instead of product=-1; you could write product--, and instead of product = producttemp.get(j); it could be product = temp.get(j);. Your way isn't necessarily bad, but the alternatives are more common and easier to read.

Declare variables where they are used

You are declaring double sqrt; a lot earlier than you need sqrt, which makes your code harder to read. Same for product.

For loop with two indices

This for loop: for(long i=A,k=0;i<=B && k<(B-A+1);i++,k++) is extremely hard to understand.

Luckily, you can just remove k. The stop condition is already covered by i.

Enhanced for loops

If you use for (Long currentTemp : temp) { you can get rid of the j variable.

Functions and Tests

main really should only be responsible for starting your program, nothing else. Extract the code to a separate function, that way, you can also easily test it. To use unit tests, it would also be useful if you returned a result from a function instead of printing it directly.

You should also extract other functionality to its own function. For example, everything inside the while loop could go in its own function.

Different Approach

When getting a question like this, I wouldn't put everything in one big method. If you read the question, it becomes obvious that you need something to create the product of digits. So create a product method. You also need something to check if a number is a perfect square, so create that method as well (isPerfectSquare). Lastly, create a method to check if a number contains zero (containsZero).

Then, just create the main method and combine everything:

public static long run(long A, long B, long K) {
    int satisfiedConditionCount = 0;
    for (long i = A; i <= B; i++) {
        if (!containsZero(i) && isPerfectSquare(product(i))) {
            satisfiedConditionCount++;
            if (satisfiedConditionCount == K) {
                return i;
            }
        }
    }
    return -1;
}

public static long product(long number) {
    long product = 1;
    while (number != 0) {
        number /= 10;
        product *= number % 10;
    }
    return product;
}

public static boolean isPerfectSquare(long number) {
    int sqrt = (int) Math.sqrt(number);
    return sqrt * sqrt == number;
}

public static boolean containsZero(long number) {
    return String.valueOf(number).contains("0");
}

Now the code is a lot more readable, and because it is in separate functions, you could profile it to find bottle necks, and then improve on those.

Another added benefit of separate functions (apart from the readability, reusability, and profiling) is that you can test them separately.

StackExchange Code Review Q#67142, answer score: 8