Find the Least Number Sums of Perfect Squares

in #whereinlast month

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Mathematically proven that we need at most up to 4 perfect squares that can be sum up to any positive integers. We also known in this post that we can use Dynamic programming to compute the least number of perfect square numbers that sum up to n.

The DP equation is:

f(0) = 0
f(i) = min(f(i), f(i - j * j); // for j * j <= i

To print which perfect square numbers are summing up to N, we can use another array to record the last perfect square and then keep tracking back last perfect squares until nothing remained. This works because of the inherent Dynamic Programming characteristics - the sub problems are also optimial.

The following Python solution prints the solution to the least number of perfect square sums, for example: 1234 = sqr(3) + sqr(35).

def computeMinSquare(N):
    M = 100000 # marks as not-visited
    ans = [M] * (N+1)
    last = [0]* (N+1)
    ans[0] = -1
    for i in range(1, N+1):    
        for j in range(i):
            if (i &gt;= j * j) and ans[i - j*j] != M and (ans[i] > ans[i-j*j]+1):
                last[i] = j  # remember the perfect square
                ans[i] = min(ans[i], ans[i - j * j] + 1) # DP Equation
    s = []
    j = N
    while (j > 0) and (last[j] > 0):
        a = last[j]
        s.append("sqr("+str(a) + ")")
        j = j - last[j]*last[j]
    print(str(N) + " = " + " + ".join(s))

# prints 1234 = sqr(3) + sqr(35)
computeMinSquare(1234)

--EOF (The Ultimate Computing & Technology Blog) --

Reposted to Computing Technology


Follow me for topics of Algorithms, Blockchain and Cloud.
I am @justyy - a Steem Witness
https://steemyy.com

Steem On!~
Every little helps! I hope this helps!


If you like my work, please consider voting for me or Buy Me a Coffee, thanks!
https://steemit.com/~witnesses type in justyy and click VOTE



Alternatively, you could proxy to me if you are too lazy to vote!

Also: you can vote me at the tool I made: https://steemyy.com/witness-voting/?witness=justyy

Sort:  

thanks for new update

Coin Marketplace

STEEM 0.16
TRX 0.03
JST 0.026
BTC 12892.46
ETH 396.32
USDT 1.00
SBD 0.99