daiict's blog

problem on dynamic programming
By daiict, history, 8 years ago, In English

Can anyone help me on the following problem of dynamic programming.Problem statement is as follows: Given a number n find the least number of perfect square numbers sum needed to get n. E.g.

n = 12, return 3 (4 + 4 + 4) = (2^2 + 2^2 + 2^2) NOT (3^2 + 1 + 1 + 1)

n =6, return 3(4 + 1 + 1) = (2^2 + 1^2 + 1^2)

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Well, I'm not sure if my dp approach is the best one, but you can solve it in the following way:

*If n is a perfect square, then dp(n) = 1

*Iterate over 1², 2², ..., k² where k² is the greater perfect square less than n. Then, you just need to write dp(n) = 1 + min(dp(n-i²)).

The complexity of this dp solution would be O(n sqrt(n))

However, It can be solved if you know some math facts.

*It is known that every natural number can be represented as a sum of 4 four perfect squares. So, your answer will always be at most 4. It makes it easier. https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem

*It is known that a natural number can be represented as a sum of three perfect squares if and only if it is not of the form 4^a(8b + 7) https://en.wikipedia.org/wiki/Legendre%27s_three-square_theorem

*Finally, it is not difficult to realize that a number can be represented as a sum of two perfect squares if and only if every prime factor which is 3mod4 has even exponent in the factorization of n.

Therefore, using these facts, you can solve it in the following way:

  • If n is a perfect square , ans = 1
  • else If every prime divisor 3mod4 has even exponent , ans = 2
  • else If n is not of the form 4^a(8b + 7) , ans = 3
  • Else ans = 4

The complexity of this algorithm would be O( sqrt(n) ) just to get the prime factors(Of course, you can do Sieve of Eratosthenes)

Also, notice that the last approach can help you to solve the version in which you are given a list of numbers and you need to solve the problem for each number on the list. In this case, you can do Sieve of Eratosthenes first, and then, you can mark the numbers on the list and iterate over all numbers divisible by a prime 3mod4.( For the 2nd step of the algorithm, it is clear that 1st and 3rd steps are O(logn)). So, the total complexity in this case would be O(mlogm) where m is the maximum number on the list.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    OPSSSSS...sry :O

    And also thank you for your useful comment...I didn't know each of these :grin:

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    @Lucas_97, can you explain how can we check whether n is of the form 4^a(8b+7) or not in an efficient way.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      First, divide n by 4 as many times as you can. In the end, if n % 8 = 7 then it has the desired form, otherwise, it is not of that form.

      while(n % 4 == 0) n /= 4; if(n % 8 == 7) It is of the form 4^a(8b + 7) else It is not of that form

      → Reply