Fal Alexandr Fal Alexandr - 6 months ago 25
Java Question

Is there any algorithm for number decomposition?

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.

Given N, return X, such that

X > N, X - simple, X - palindrome

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;
}

Lee Lee
Answer

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.