Finding numbers whose product of the digits are perfect squares

Question

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 < cases)
    {
        A = in.nextLong();
        B = in.nextLong();
        K = in.nextLong();
        ArrayList<Long> products = new ArrayList<>();
        long product = 1;
        for(long i=A,k=0;i<=B && k<(B-A+1);i++,k++)
        {
            long num = i;


            double sqrt;

            ArrayList<Long> 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++;
    }
}
}

Answer 1

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 = product*temp.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.

Answer 2

Problems like this usually do not go well with a straightforward approach. The most expensive part of the solutions above is the necessity to recompute digits of a very long number after each increment. The second most expensive part is testing for a perfect square. Both can be avoided if you keep the number in its string representation.

Notice that a number is a perfect square if the digits 5 and 7 appear an even number of times, combined appearances of 3 and 6 are even, and combined appearances of 2, 6, 8 are also even.

So, implement an increment for a number as a string. Maintain an array for digit counts. Test the perfect square condition outlined above.

A perk benefit of the suggested solution is that it scales well beyond the limits of the problem statement.

Answer 3

this code should take 1/12th the time its taking now ( — comment)

To build on what vnp said: you will need a change of algorithm.

Follow this line of reasoning:

• Any integer has a prime factorisation: \$6 = 2^1 \times 3^1\$
• Multiplying integers is identical to adding the powers of their prime factorisations: \$6 \times 8 = 2^1 \times 3^1 + 2^3 \times 3^0 = 2^{3+1} \times 3^{0+1} = 2^4 \times 3^1 = 48)\$
• An integer is a perfect square iff its prime factorisation's powers are all even.

Since you're working with the product of single digits, you have a very bounded input for factorisation (see bottom). It's cheap to keep track of the prime factor powers when a digit changes.

You can take it a step further: you don't even need to store the actual prime powers, just whether they are odd or even. 4 bits will do: a bit each for 2, 3, 5, and 7, the only single-digit primes.

Here is an outline of how the code would work:

byte[] bcdnum // current number in BCD notation: 0-9
BitSet odds // bit set if corresponding power is odd
initialise(low)
from low to high :
  increment(bcdnum, odds)
  if odds.isEmpty() :
    sequence -= 1
    if sequence == 0 :
      print bcdnum
      exit
print -1

increment flips the bits on odds as it increments digits. It looks at the difference of prime factors between the digit it comes from, and the digit it is setting (always one higher, except with nine), and flips the relevant bits if their difference is odd.

For instance, going from 2 to 3 means flipping 2 and flipping 3. Going from 4 to 5 means just flipping 5, because 4 = 2² , an even power.

Here's an example implementation:

static final int POW2 = 0, POW3 = 1, POW5 = 2, POW7 = 3;
void increment() {
  int i = 0;
  for (;;) {
    final int digit = bcdnum[i]++;
    switch (digit) { // digit -> digit + 1
      case 0: break;

      case 1: odds.flip(POW2); break;
      case 2: odds.flip(POW2); odds.flip(POW3); break;
      case 3: odds.flip(POW3); break;
      case 4: odds.flip(POW5); break;
      case 5: odds.flip(POW2); odds.flip(POW3); odds.flip(POW5); break;
      case 6: odds.flip(POW2); odds.flip(POW3); odds.flip(POW7); break;
      case 7: odds.flip(POW2); odds.flip(POW7); break;
      case 8: odds.flip(POW2); break;

      case 9:
        bcdnum[i++] = 1; // skip zeroes
        continue; // loop to next digit

      default: throw new IllegalArgumentException("unexpected digit: " + digit);
    }

    break; // done incrementing; break loop
  }
}

---

Digit prime factors:

      2   3   5   7
    +---+---+---+---+
  1 | _ | _ | _ | _ |
+---+---+---+---+---+
  2 | 1 | _ | _ | _ |
    +---+---+---+---+
  3 | _ | 1 | _ | _ |
+---+---+---+---+---+
  4 | 2 | _ | _ | _ |
    +---+---+---+---+
  5 | _ | _ | 1 | _ |
+---+---+---+---+---+
  6 | 1 | 1 | _ | _ |
    +---+---+---+---+
  7 | _ | _ | _ | 1 |
+---+---+---+---+---+
  8 | 3 | _ | _ | _ |
    +---+---+---+---+
  9 | _ | 2 | _ | _ |
+---+---+---+---+---+