Fal Alexandr - 1 year ago 80

Java Question

Recently I faced "2 easy problems, which can be solved in an hour". I'm not really familiar with competitive programming, so it wasn't that easy for me, and I came up only with brute force methods, so now I'm interested if my solution even works and if there is better solution.

The problem was:

*Given N(2 digits or more), find minimal number such that the product of its digits equals to N. If it's impossible, return 0.*

My solution in java looked like this

`int getNumber(int N) {`

int i = 25;

while(i < Integer.MAX_VALUE) {

if(digitsMult(i) == N)

return i;

i++;

}

return 0;

}

Also would be nice if you could check the second problem as well.

Here I used brute force as well

`int getPrimePalindrome(int N) {`

int i = N;

while(i < Integer.MAX_VALUE) {

if(isPalindrome(i))

if(isPrime(i))

return i;

i++;

}

return 0;

}

boolean isPalindrome(int n) {

String num = Integer.toString(n);

String reverse = new StringBuffer(n).reverse().toString();

return num.equals(reverse);

}

boolean isPrime(int n) {

if(n == 2)

return true;

if(n % 2 == 0)

return false;

for(int i = 3; i*i <= n; i+=2)

if(n % i == 0)

return false;

return true;

}

Answer Source

This kind of question is very common for coding interviews. 'Brute forcing' as you put it is the only way, however, I think what they are looking for is clever optimisations,

For example your `isPalindrome`

can be more efficient - you only need to check the first half matches the end half reversed, not the whole thing.

Secondly, you don't want to be calculating your prime stack inside the inner loop every single time. I would move `isPrime`

to be the outer `if`

which would allow you to maintain the complete list of primes and not have to calculate it each time.