Solution of 11407 - Squares

Problem Description
source: http://uva.onlinejudge.org/external/114/11407.html

For any positive integer N, N = a 2 1 + a 2 2 + . . . + a 2 n that is, any positive integer can be represented as sum of squares of other numbers. Your task is to print the smallest ‘n’ such that N = a 2 1 + a 2 2 + . . . + a 2 n.

Input

The first line of the input will contain an integer ‘t’ which indicates the number of test cases to follow. Each test case will contain a single integer ‘N’ (1 ≤ N ≤ 10000) on a line by itself. 


Output 

Print an integer which represents the smallest ‘n’ such that N = a 2 1 + a 2 2 + . . . + a 2 n.

Explanation for sample test cases: 
5 → number of test cases
1 = 12 (1 term) 
2 = 12 + 12 (2 terms) 
3 = 12 + 12 + 12 (3 terms) 
4 = 22 (1 term) 
50 = 52 + 52 (2 terms) 

Sample Input

 5 1 2 3 4 50

Sample Output 

1 2 3 1 

Solution:

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include<stdio.h>
#include<stdlib.h>

using namespace std;

int main()
{
    int i,j,t,n,s,value[10005],c,minValue;
    value[1]=1;value[2]=2;value[3]=3;value[4]=1;
    for(i=5;i<10001;i++)
    {
        s=sqrt(i);
        c=1000;
        for(j=s;j>0;j--)
        {
            minValue=value[i-(j*j)]+1;
            if(c>minValue)
                c=minValue;
        }
        value[i]=c;
    }
    //freopen("in.txt","r",stdin);
    while(scanf("%d",&t)==1)
    {
        for(i=1;i<=t;i++)
        {
            scanf("%d",&n);
            printf("%d\n",value[n]);
        }
    }
    return 0;
}