Fal Alexandr - 2 years ago 93
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;
}
``````

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.