Algorithm to solve an equation

Question

I have this problem for the course "Algorithm and data structures"

You have a equation x^2+s(x)+200·x=N, where x and N are natural numbers and S(x) is the sum of digits of number x.

On the input we have N and A, B such that A≤B and A, B≤1,000,000,000. You need to check if there is a natural number x in the interval [A, B] that solves the equation. If found you need to return that number, otherwise return -1.

Example Input:

    1456
    10 80

Output
    
    -1

I managed to solve this problem by using some math and a bit modified version of brute force algorithm. But are there any more effective(algorithm based) ways to solve this problem?

This is my code:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Range {
    
    static int proveri(long N, long A, long B) {
        long res = 0;
        long start = (long)((-200 + Math.sqrt(4*N + 4))/2);
        //System.out.println(start);
        for (long i = Math.max(A, start); i <= B; i++) {
            res = i * i + S(i) + 200 * i;
            if(res == N)
                return (int)i;
            if(res > N)
                return -1;
        }
        
        return -1;
    }
    
    static int S(long x) {
        int sum = 0;
        while(x > 0) {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }
    
    public static void main(String[] args) throws Exception {
        int i,j,k;
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        long N = Long.parseLong(br.readLine());
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        
        int res = proveri(N, A, B);
        System.out.println(res);
        
        br.close();
        
    }
    
}

Answer 1

Here's a way where you can cut down on the amount of numbers you have to search.

Consider the equation a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀ = 0. The rational root theorem states that if x = p/q is a solution, then p divides a₀ and q divides a_n

In your case, a_n is 1 and a₀ is equal to S(x)-N. Thus, we know that any solution must divide S(x)-N.

This is where ben75's tip comes in. Since S(x) can't be bigger than 81, we can loop through all of the possible values of S(x), and solve separately. Something like this:

for each possible value of S(x)
    loop through every factor x of S(x) - N
    check if it is between A and B, if its digits sum to S(x)
    and if it is a solution to x*x + 200x + S(x) = N.
        if it is, return it.

return -1

There's also a pretty slick way for you to loop through all of the factors of a number, but I'll let you work that one out for yourself since this is for a course. My hint there is to look at the prime factorization of a number.

Answer 2

For the equation x^2+s(x)+200·x=N, consider

x^2 + 200·x + (N - s(x)) = 0

For a solution to a*x^2 + b*x + c = 0 equation with integer solutions, we need to have:

b^2 - 4*a*c >= 0 and must be a perfect square

Hence 200^2 - 4 * (N - s(x)) >=0 and a square or

10000 >= (N - s(x)) and (10,000 - (N - s(x)) must be a square. The square value is therefore less than 10,000 and hence there can be at most 100 values you need to check. With proper values of N it can be much lesser.

Also note that since N < 10,000, s(x) can be at most 36. These should cut down the range quite a bit.