yanis February 2016

Algorithm for finding the smallest number of precise squares which amount is n

I am supposed to write a function with one argument n and the function should count the smallest number of precise squares which amount is n. For example if n=10, the function should return 2 (10=32 +12). So far i have implemented some solution- using dynamic programming but I am not absolutely sure of its correctness:

Squares(n)
  dyn[0...n]
  dyn[0] <- 0 

  for k <- 1 to n
       dyn[k] <- k+1
       i <- 1
       j <- 1

       while j<=k do
          if dyn[k-j] < dyn[k]
               dyn[k] <- dyn[k-j]
          i <- i+1
          j <- i*i

      dyn[k] <- dyn[k]+1
   k <- n

   return dyn[n]

Please, analyze my solution and if you can provide faster one? So far its running time is O(n3/2).

Answers


Salvador Dali February 2016

You do not need any of this. You have to know some math stuff.

  1. Some numbers are already squares int(sqrt(x))**2 == x
  2. Some numbers can be represented as sum of 2 squares (Fermat)
  3. Some numbers can be represented as sum of 3 squares (Legendre)
  4. Every number can be represented as sum of 4 squares (Lagrange)

    So just check first two conditions and if non of them holds - return 4.

Post Status

Asked in February 2016
Viewed 1,545 times
Voted 7
Answered 1 times

Search




Leave an answer