conceptual problem

[nitin1]

x^2 + S(x)*x - n=0 where n can be till 10^8 interger . and s(x) is the sum of the digits of the x integer. we have to print the value of x for which this equation holds otherwise print -1. my answer is taking too much time with brute force. can anyone give any hint ?

[Gonbe]

Hmm how do you brute force it currently? Some optimizations (but it's still brute forcing) would be to:

• don't count the amount of digits per attempted number (or maybe not at all) instead start at i=10, j = 1 where you multiply i by 10 everytime your number hits i and increment j. j would be the S(x)

• Because you can determine S(x) somewhat cheap (I think the difference of looping you'll get gains you more than you lose by keeping track of j) you could use it to lower the search domain. You should search until sqrt(n) - x*j. You should probably also search from that number going down instead of starting from 0 and going up.

This is probably something you've tried already, at first thought I wouldn't know a proper optimization (Maybe look for a low point under which is no longer useful to search, or number to skip based on previous results)

-edit-
Hmm misread S(x) as the digit count instead of the sum of digits. Maybe treat S(x) in the lowest case with a value of 1 and then search till sqrt(n) - x

[nitin1]

can you explain how are you doing i=10, j=1 and multiply i by 10 each time thing ? what is your number in your explainations ?

secondly, please explain that ahy should i read till sqrt(n)-x ? what is x in this ?

[Gonbe]

X is the number you are looking for and n is the given number you should solve the equation for.

x^2 + S(x)*x - n = 0

can be rewritten as

n = x^2 + S(x)*x

Now, what happens x would happen to be sqrt(n)? It would say the following:

n = (sqrt(n))^2 + S(sqrt(n))*sqrt(n)
  = n + S(sqrt(n))*sqrt(n)

So you're basically saying n equals n + 'something' which can never be true as X is a positive integer so it will only be bigger. Ignore the reply containing i/j it is based on a false interpretation of the assignment. I left it there in case it might be useful but I don't think it will be.

You'll want to discover something about S(x)*x to find the point where it's useless to continue. You can stop searching when the following condition is true for all x that follow:

S(x)*x > n - (x^2)
= S(x) > (n - (x^2)) / x
= S(x) > n/x - x

At what point does that become true though? If it some point this condition is met, it needn't be the case for x's following it. While the sum of digits does grow in a pattern it "drops" every now and then but it starts at a higher point than where the previous drop started of the same digit count. Maybe you can think of something for this. (or S(x)*x will always be bigger than n-(x-2) if that proves to be easier)

Example:

Say you want to know x for n = 484 you don't want to check 0-484. You needn't check higher than sqrt(484) = 22. You can actually stop at 20 though. while it only matters two iterations for this it will matter more on big numbers. (but it's always the question if calculations required don't mitigate the potential performance gain)