The range for a,b,c would be 0 to sqrt(n). Iterating over all values would give complexity O(n^(3/2)).
Using bitmaps, we can determine which numbers within 0..n are not in the list of a^2 + b^2 + c^2.
I guess, here we need to assume that we have O(n) space atleast.
For making computationally effi
I have a slight improvement O ( n^2 log (n ) )Say you have a^2 + b^2 + c^2 = d.Keep a sorted list of all possible a^2 + b ^ 2 ... this would take n^2 time to generate and n^2 log n to sort. Now loop over all possible 'd' and 'c' and compute d - c ^ 2. Use binary search to determine whether that
backtracking, I'm not sure about the complexity.Greetings.On 10/31/06, Karthik Rathinavelu <[EMAIL PROTECTED]
> wrote:Question: Given n, find the numbers in the range of 0...n which CAN'T be represented in the form of sum of squares of 3 non-negative numbers.
If anyone could possibly give a solutio
