# 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 < 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)
{
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)

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

caseNum++;
}
}
}

• Running with A = 10^16, B = 10^18, K = 10^7 will generate a huge amount of numbers that all have zeros in them. Trying each number is not going to work, you need a completely different approach. – fgb Oct 18 '14 at 20:22
• I'm thinking something like generating the square numbers first and then factorizing them to get the digits, or taking advantage of the fact that the order of the digits doesn't affect their product. – fgb Oct 18 '14 at 20:25

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.

• thanks for all the suggestions, I ve already modified my code but this code should take 1/12th the time its taking now... any suggestions ? – Aditya Verma Oct 18 '14 at 19:00
• Note that the shorthand operators += -+ *= /= behave slightly different than the long variants. They perform casting: "A compound assignment expression of the form E1 op= E2 is equivalent to E1 = (T)((E1) op (E2)), where T is the type of E1, except that E1 is evaluated only once." Something one need to be aware of, in my opinion. – Bobby Oct 18 '14 at 19:19
• we kinda goin off topic , aren't we ? :/ – Aditya Verma Oct 18 '14 at 19:24
• @Bobby It doesn't seem to make a difference in this case, but yes, its good to be aware of. AdityaVerma: see my edit – tim Oct 18 '14 at 19:31
• @tim You wrote 'instead of product=-1; you could write product--'. I think you misread what the poster wrote. He didn't write product -= 1; (and neither did you!), but product = -1;. It's an assignment, not a decrement. This is a good reason the use more white space! – user1118321 Oct 19 '14 at 1:03

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.

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.

• 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 | _ | _ |
+---+---+---+---+---+