Algorithm of 11407 - Squares

Problem Description Link
Algorithm:

This is a simple problem  to solve this problem you can pre generate the number of minimum terms for all integer from 1 to 10000 and get input and check from array how many  term needed and print the value.

Process:

 For any positive integer N , N = a12 + a22 +...+ an2 that is, any positive integer can be represented as sum of squares of other numbers.

For example you know minimum term of 1,2,3,4 and based on this value calculate others  5 to 10000 value term

1

2

3

1

2

3

4

2

1

2

1                    2                        3              4                              5              6              7                              8              9              10

For 5

S=sqrt(5)=2

Way    2²+1²=5 so 2 term

And  1²+2²=5 so 2 term

Min value=2

So

Loop from ( s=2 to 1)

 array[5- 2*2]+1=2  because 2² =4  and (5-1)=1  we know term of 1=1 so 2² is 1 term and for 1 need 1 term so total term=(1+1)=2

array[5- 1*1]+1=2  because 1² =1+1²  we know term of 1=1 so 2² is 1 term and for 1 need 1 term so total term=(1+1)=2

so array[5]=2;

For 10

S=sqrt(10)=3

Loop from (3 to 1)

Array[10-3*3]+1=2

Array[10-2*2]+1=4

Array[10-1*1]+1=2  so min =2 so array[10]=2