## Google Interview Question for Software Engineer / Developers

Country: Israel
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
of 3 vote

Since nobody has solved the math portion, let me explain that to use the mathematical lemma that for any positive integer N there is at least one representation of N with at 4 or less squares, we can define nonnegative integers a, b, c, and d such that a>=b>=c>=d. Without proof I claim the following: a must lie in the range {floor(sqrt(N)),ceil(sqrt(N/4)}, b must lie in the range {floor(sqrt(N-a*a)),ceil(sqrt((N-a*a)/3)}, c must lie in the range {floor(sqrt(N-a*a-b*b)),ceil(sqrt((N-a*a-b*b)/2))}, and d must equal N-a*a-b*b-c*c. As a result this reduces our problem to finding values of a, b, and c within these given ranges to find the minimum solution. We already know it is possible to represent N with 4 squares so the goal is instead we can focus on finding values of a and b such that N-a*a-b*b is the square of an integer because if this is true then we can represent N as 3 or less squares. The time complexity of the algorithm becomes O(sqrt(N)*sqrt(N)) which is equivalent to O(N) because we only need to iterate over values of a and b. Also we can exit the function early if N is the square of an integer, otherwise we can exit early if there exist a and b such that N=a*a+b*b. If we use the Math.sqrt function then this might cause floating point errors, but to make things simpler I will assume we can ignore this for now. The following Java code implements this strategy:

``````public static int minSquares(int N) {
int K = 4;
for (int a = (int)Math.sqrt(N); i >= (int)Math.sqrt(N/4.0); i--) {
int aSquared = a*a;
if (aSquared == N) {
return 1;
}
for (int b = (int)Math.sqrt(N-aSquared); b >= (int)Math.sqrt((N-aSquared)/3.0); b--) {
int bSquared = b*b;
int currSum = aSquared + bSquared;
if (currSum == N) {
return 2;
}
int cSquared = N - currSum;
double c = Math.sqrt(cSquared);
if (c == Math.floor(c)) {
K = 3;
}
}
}
return K;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Does not work for 72.

Comment hidden because of low score. Click to expand.
0

why do you say it does not work for 72? it works, it is a correct solution, voted up

Comment hidden because of low score. Click to expand.
0

Thanks for this idea! It works with any number and it is *much* better than the DP solution which is O(N.sqrt(N)) and requires O(N) additional memory! This idea, on the other hand, is much more efficient:

``````➜   time java SumOfSquares 2000000000000 (i.e. 2 trillion)
2000000000000 = 1414208^2 + 3840^2 + 960^2 + 256^2
java SumOfSquares 2000000000000  0.13s user 0.02s system 113% cpu 0.134 total``````

With DP solution on my computer:

``````time java SumOfSquares 20000001 (this is just 2 million and 1)
20000001 = 1^2 + 464^2 + 4448^2
sum of squares = 20000001
java SumOfSquares 20000001  466.52s user 1.00s system 99% cpu 7:48.22 total``````

Better algorithm wins, always!

Comment hidden because of low score. Click to expand.
1
of 1 vote

DP solution, any comments? Works for given numbers, including 12.

``````def squares(n):
results = [0] * (n + 1)
squares = []
for i in range(1, n + 1):
if i ** 2 <= n:
squares.append(i)
count = i
for j in [r for r in squares if r ** 2 <= count]:
if results[i - j ** 2] + 1 < count:
count = results[i - j ** 2] + 1
results[i] = count
return results[n]``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Simple recursive solution in C#:

``````public static int findMinSquares(int num)
{
if (num == 1 || num == 0) return num;

int min = int.MaxValue;
for (int i = 1; i <= (int)Math.Floor(Math.Sqrt(num)); i++)
{
min = Math.Min(min, 1 + findMinSquares(num - (i * i)));
}
return min;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Greedy solution with memoization.
(Here I omit test if N is out of memo array bounds)

``````public class problem_5 {
private int[] _memo;

public int getK(int N){
double n = (double)N;
int result = 0;
while(n != 0.0){
if(_memo[(int)n] != 0){
result += _memo[(int)n];
break;
} else {
double maxLessSquare = Math.floor(Math.sqrt(n));
n = n - (maxLessSquare * maxLessSquare);
result += 1;
}
}
_memo[N] = result;
return result;
}

public problem_5(){
int memoSize = 1000;
_memo = new int[memoSize];
for(int i = 0; i < memoSize; i++)
_memo[i] = 0;
}

public static void main(String [] args){
problem_5 p = new problem_5();
System.out.println(p.getK(15));
System.out.println(p.getK(9));
System.out.println(p.getK(8));
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

I don't think this solution would work if N equals 12 because 12= 4+ 4+ 4 so K should equal 3, but the greedy solution would output 4.

Comment hidden because of low score. Click to expand.
0

Here you are creating an array of size 1000, I don't think you would need to

Comment hidden because of low score. Click to expand.
0
of 0 vote

The following code prints K, as well as the list of integers whose square leads to N.

``````import java.lang.Math;

class SumOfIntegerSquares {
int N;
int [] memArray;
int [] tracker;

public static void main(String [] args) {
new SumOfIntegerSquares().printAsSumOfIntegerSquares(2000);
}

public void printAsSumOfIntegerSquares(int N) {
this.N = N;
memArray = new int[N + 1];
tracker = new int [N + 1];
int K = getK(N);
System.out.println("K = " + K);
printNumbers(N);
}

private void printNumbers(int N) {
if (tracker[N] == N) {
System.out.print((int)(Math.sqrt(N)) + ", ");
}
else {
printNumbers(tracker[N]);
printNumbers(N - tracker[N]);
}
}

private int getK(int n) {
//System.out.println("N = " + n);
if (memArray[n] != 0) {
return memArray[n];
}
int sqrtN = (int)Math.sqrt(n);
//System.out.println("Sqrt = " + sqrtN);
if (n == sqrtN * sqrtN) {
memArray[n] = 1;
tracker[n] = n;
}
else {
int minimum = Integer.MAX_VALUE;
int minI = 0;
for (int i = 1; i < n; i++) {
int temp = getK(i) + getK(n- i);
if (temp < minimum) {
minimum = temp;
minI = i;
}
}
memArray[n] = minimum;
tracker[n] = minI;
}
return memArray[n];

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple recursive solution:

``````int FindMinSquare( int n )
{
if ( n <= 0 )
{
return 0;
}

int i = 1;

while ( i*i <= n )
{
current_answer = FindMinSquare( n - i*i );

{
}
i++;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

This is my solution , but don't know about its time complexity . Someone please suggest.

``````int total( int n ){
if ( n <= 0 )
return 0;
if( n == 0 || n == 1 )
return n;

int x = sqrt(n);
int minv = INT_MAX;

for( int i = x ; i>= 1; i--)
{
minv =  min( minv, 1 + total(n-i*i) );
}
return minv;
}``````

Comment hidden because of low score. Click to expand.
0

I believe it's O(n^2)

Comment hidden because of low score. Click to expand.
0

- 1st recursion: N^(1/2)
- 2nd recursion: N^(1/4)
- 3rd recursion: N^(1/8)
......
Total: 1/2+1/4+1/8+ ...... = 1
So it is O(N) computation complexity and O(1) space complexity.

Comment hidden because of low score. Click to expand.
0

I stand corrected, it way worse,
f(n) = f(n-1) + f(n-2) + f(n-4) + ....+ f( n - i*i) where ( i*i <=n ) and ( (i+1)*(i+1)>n )
f(n) = O(2^n)

Comment hidden because of low score. Click to expand.
0

I don't think your sub-problem is correct. It is minimization problem.
F(n) = 1 + min{F(n-i*i)}, where i <= sqrt(n).

Comment hidden because of low score. Click to expand.
0

@peter:
Please note that we call Total(n-i*i) for every i >0 and i <sqrt(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

public int leastSqr(int a)
{
int j, k;
int min;
int[] list = new int[a+1];
list[0] = 0;
for(k = 0; k <= a; k++)
{
int i = (int)Math.sqrt(k);
if(i > 0 && i*i == k)
list[k] = 1;
else
{
min = Integer.MAX_VALUE;
for(j = 1 ; j <= k/2; j++)
{
int sum = list[k-j] + list[j];
if(sum < min)
min = sum;

list[k] = min;
}
}
}
return list[k-1];
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public int leastSqr(int a)
{
int j, k;
int min;
int[] list = new int[a+1];
list[0] = 0;
for(k = 0; k <= a; k++)
{
int i = (int)Math.sqrt(k);
if(i > 0 && i*i == k)
list[k] = 1;
else
{
min = Integer.MAX_VALUE;
for(j = 1 ; j <= k/2; j++)
{
int sum = list[k-j] + list[j];
if(sum < min)
min = sum;

list[k] = min;
}
}
}
return list[k-1];
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hinted from "Source"'s recursive solution, this is my DP solution. Time complexity is O(n^(1.5)), space complexity is O(n)

``````int total(int n){
if(n<2) return n;
vector<int> dp(n+1, 0);
dp[1] = 1;
for(int i=2; i<=n; ++i){
int minv = INT_MAX;
for(int j=1; j<=sqrt(i); ++j){
minv  = min(minv, 1+dp[i-j*j]);
}
dp[i] = minv;
}
return dp[n];
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

int findMinSquares(int n)
{
std::vector<int> memo(n + 1);
memo[0] = 0;
for (int i = 1; i <= n; ++i) {
memo[i] = 4;
for (int j = ceil(sqrt(i) / 2); j <= sqrt(i); ++j)
memo[i] = std::min(memo[i], memo[i - j * j] + 1);
}

return memo[n];
}

Comment hidden because of low score. Click to expand.
0

The most beautiful answer so far, it doesn't have recursive calls and the number of iterations is quite small, great job Diana

Comment hidden because of low score. Click to expand.
1
of 1 vote

Beautiful, really? O(N^(1.5)) computation complexity and O(N) space complexity.

Comment hidden because of low score. Click to expand.
0

I've written the same solution excepting I didn't use the sqrt(i) - but instead checked s = j*j < i each iteration which is a small optimization. Then I described why time complexity is O(N^1.5) - since w're iterating N times in the outer cycle and sqrt(i) times in the inner one complexity will be ~ sum(sqrt(i)), i = 1..N. Then interviewer explained me that there is a maximum possible amount of 4 components, I proposed to do the recursive solution - I smoothly estimated its complexity >=O(n) and <=O(n^1.5). Interviewer had no more questions, but then he gave me a bad feedback about bad coding and analytical skills, I don't know why...

Comment hidden because of low score. Click to expand.
0
of 0 vote

I performed extensive research on this, so far two methods have been proposed:
1- using recursion: requires O(1) space, but has a lot of recursions
2- using a loop (proposed by Diana and others: O(n) space and the number of iterations is much lower than recursive solution.

I have found a recursive solution that in terms of iterations is far better using the loop, here is the code:

``````#include "stdafx.h"
#include "math.h"
#include <vector>

// method proposed by Diana
int FindMinSquaresLoop(int n, int& iterations)
{
std::vector<int> memo(n + 1);
memo[0] = 0;
iterations = 0;
for (int i = 1; i <= n; ++i) {
memo[i] = 4;
int Sqrt = (int)sqrt((double)i);
for (int j = (int)ceil(Sqrt / 2.0); j <= Sqrt; ++j)
{
iterations++;
memo[i] = std::min(memo[i], memo[i - j * j] + 1);
}
}

return memo[n];
}

int FindMinSquaresRecursive(int n, int depth, int& iterations, int best_so_far)
{
iterations++;

if ( sqrt((double)n) == floor(sqrt((double)n)) )
{
return 1;
}

// if a better solution canot be found, give up
if ( depth + 1 >= best_so_far )
{
return best_so_far;
}

int current_min_square;

int i;

for ( i = (int)(floor(sqrt( (double)n ))) ; i >=1 ; i-- )
{
if ( i*i > n )
{
break;
}
else
{

current_min_square = 1 + FindMinSquaresRecursive( n - i*i, depth+1, iterations, best_so_far );
if ( current_min_square < best_so_far )
{
best_so_far = current_min_square;
}
}
}

return best_so_far;
}

int _tmain(int argc, _TCHAR* argv[])
{
int depth = 0;
int iter_recursive;
int iter_loop;
int total_iter_recursive = 0;
int total_iter_loop = 0;
int MinSquaresRecursive, MinSquaresLoop;
int i;

printf("Number, MinSquaresLoop, iterations_loop, MinSquaresRecursive, iterations_recursive\n" );
for ( i = 1; i < 100 ; i++ )
{
iter_recursive = 0;
iter_loop = 0;
MinSquaresRecursive = FindMinSquaresRecursive( i, depth, iter_recursive, 4 );
MinSquaresLoop = FindMinSquaresLoop( i , iter_loop );

total_iter_recursive += iter_recursive;
total_iter_loop += iter_loop;

printf("%d,%d,%d,%d,%d\n", i, MinSquaresLoop, iter_loop ,MinSquaresRecursive, iter_recursive  );
}
printf("Total iterations recursive: %d, Total iterations loop: %d\n", total_iter_recursive, total_iter_loop );
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

and here is the output of the program for the first 100 numbers

Number, MinSquaresLoop, iterations_loop, MinSquaresRecursive, iterations_recursive
1,1,1,1,1
2,2,2,2,2
3,3,3,3,3
4,1,5,1,1
5,2,7,2,3
6,3,9,3,6
7,4,11,4,8
8,2,13,2,3
9,1,15,1,1
10,2,17,2,4
11,3,19,3,10
12,3,21,3,11
13,2,23,2,4
14,3,25,3,12
15,4,27,4,16
16,1,30,1,1
17,2,33,2,5
18,2,36,2,6
19,3,39,3,17
20,2,42,2,5
21,3,45,3,18
22,3,48,3,19
23,4,51,4,32
24,3,54,3,18
25,1,57,1,1
26,2,60,2,6
27,3,63,3,23
28,4,66,4,34
29,2,69,2,6
30,3,72,3,25
31,4,75,4,42
32,2,78,2,11
33,3,81,3,26
34,2,84,2,6
35,3,87,3,28
36,1,91,1,1
37,2,95,2,7
38,3,99,3,31
39,4,103,4,53
40,2,107,2,7
41,2,111,2,9
42,3,115,3,36
43,3,119,3,39
44,3,123,3,35
45,2,127,2,7
46,3,131,3,37
47,4,135,4,72
48,3,139,3,55
49,1,143,1,1
50,2,147,2,8
51,3,151,3,41
52,2,155,2,10
53,2,159,2,8
54,3,163,3,45
55,4,167,4,82
56,3,171,3,48
57,3,175,3,45
58,2,179,2,8
59,3,183,3,47
60,4,187,4,65
61,2,191,2,14
62,3,195,3,49
63,4,199,4,91
64,1,204,1,1
65,2,209,2,9
66,3,214,3,54
67,3,219,3,56
68,2,224,2,9
69,3,229,3,56
70,3,234,3,59
71,4,239,4,126
72,2,244,2,15
73,2,249,2,9
74,2,254,2,12
75,3,259,3,62
76,3,264,3,65
77,3,269,3,61
78,3,274,3,63
79,4,279,4,147
80,2,284,2,9
81,1,289,1,1
82,2,294,2,10
83,3,299,3,66
84,3,304,3,67
85,2,309,2,10
86,3,314,3,70
87,4,319,4,147
88,3,324,3,100
89,2,329,2,12
90,2,334,2,10
91,3,339,3,74
92,4,344,4,146
93,3,349,3,77
94,3,354,3,74
95,4,359,4,172
96,3,364,3,84
97,2,369,2,10
98,2,374,2,19
99,3,379,3,78
Total iterations recursive: 3405, Total iterations loop: 15922
Press any key to continue . . .

Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this really true? "For any positive integer N, there is at least one representation of N as 4 or less squares." How can we verify it? How we can build 61 with 4 or less squares?

Comment hidden because of low score. Click to expand.
0

61 = 36 + 25

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I don't think you can.
61 = 7^2+3^2+1^2+1^2+1^2

Comment hidden because of low score. Click to expand.
0
of 0 vote

Bear in mind that this is a minimization problem. As long as we can find a K, any search is more than K can be ignored.

My idea is to find a K which is good enough initially to start with. Here is how to find the very initial K,
Here is one of case can be regards as the worst case.
- K = 0
- x = sqrt(N), N' = N - x*x and K increment to 1
- If N' < 4, K = K + N'
* If N' is equal to 3, 2, 1 or 0, then their K will be itself.
* 3 = 1+1+1; 2 = 1+1; 1 = 1; 0 - N is a square number
* return K (we call this K as K')
- Else N = N' and repeat last 2 steps

As long we found K', then any search worse than K' can be ignored. And if a solution is better than K', then can always update K' as the better so far. Carry on the rest search.

It can be proven that the initial K' is better than log2(N). Therefore the computation complexity is better than O(N^(0.5*(K' - 1))), - better than O(N^(0.5*(log2(N) - 1))). In the case of lemma (K' = 4), the computation complexity is O(N^(1.5)).

The induction of the computation complexity, please refer to the following:
cpluspluslearning-petert.blogspot.co.uk/2015/02/dynamic-programming-minimize-number-of.html

By the way the solution has O(1) space complexity.

Comment hidden because of low score. Click to expand.
0

Modification (comment editing does not work properly):

It can be proven that the initial K' is better than log2(N). Therefore the computation complexity is better than O(N^(0.5*(K' - 1))), - better than O(N^(0.5*(log2(N) - 1))). In the case of lemma (K' = 4), the computation complexity is O(N^(1.5)).

Comment hidden because of low score. Click to expand.
0

Modification (editing does not work for me):

It can be proven that the initial K' is better than log2(N). Therefore the computation complexity is better than O(N^(0.5*(K' - 1))), - better than O(N^(0.5*(log2(N) - 1))). In the case of lemma (K' = 4), the computation complexity is O(N^(1.5)).

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def function2(N, R):
if N == 0:
return R

results = []

for i in reversed(range(1, int(math.ceil(math.sqrt(N))) + 1 )):
if math.pow(i,2) <= N:
results.append( function2(N - math.pow(i,2), R + 1) )

return min(results)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def function2(N, R):
if N == 0:
return R

results = []

for i in reversed(range(1, int(math.ceil(math.sqrt(N))) + 1 )):
if math.pow(i,2) <= N:
results.append( function2(N - math.pow(i,2), R + 1) )

return min(results)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int binarySearch(ArrayList<Integer> al, int n, int start, int end)
{
while(start <=end)
{
int mid=(start+end)/2;
if(al.get(mid)==n)
return al.get(mid);
else if(mid -1 >=0 && al.get(mid) > n && al.get(mid-1) < n)
return al.get(mid-1);
else if(al.get(mid) > n)
end=mid;
else
start=mid;
}

return -1;
}

int kIntegerSquaresUtil(int n, ArrayList<Integer> al)
{
int k=0;
int len=al.size();
while(n > 0)
{
int num=binarySearch(al,n,0,len-1);
if(num < 0) return -1;
n=n-num;
k++;
}

return k;
}

int kIntegerSquares(int n)
{
ArrayList<Integer> al=new ArrayList<Integer>();

for(int i=1;i*i <= n;i++)

return kIntegerSquaresUtil(n,al);
}``````

Complexity : O(m*logm**k) where m is the number of squared numbers less than n. Which can be considered as constant.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int binarySearch(ArrayList<Integer> al, int n, int start, int end)
{
while(start <=end)
{
int mid=(start+end)/2;
if(al.get(mid)==n)
return al.get(mid);
else if(mid -1 >=0 && al.get(mid) > n && al.get(mid-1) < n)
return al.get(mid-1);
else if(al.get(mid) > n)
end=mid;
else
start=mid;
}

return -1;
}

int kIntegerSquaresUtil(int n, ArrayList<Integer> al)
{
int k=0;
int len=al.size();
while(n > 0)
{
int num=binarySearch(al,n,0,len-1);
if(num < 0) return -1;
n=n-num;
k++;
}

return k;
}

int kIntegerSquares(int n)
{
ArrayList<Integer> al=new ArrayList<Integer>();

for(int i=1;i*i <= n;i++)

return kIntegerSquaresUtil(n,al);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int binarySearch(ArrayList<Integer> al, int n, int start, int end)
{
while(start <=end)
{
int mid=(start+end)/2;
if(al.get(mid)==n)
return al.get(mid);
else if(mid -1 >=0 && al.get(mid) > n && al.get(mid-1) < n)
return al.get(mid-1);
else if(al.get(mid) > n)
end=mid;
else
start=mid;
}

return -1;
}

int kIntegerSquaresUtil(int n, ArrayList<Integer> al)
{
int k=0;
int len=al.size();
while(n > 0)
{
int num=binarySearch(al,n,0,len-1);
if(num < 0) return -1;
n=n-num;
k++;
}

return k;
}

int kIntegerSquares(int n)
{
ArrayList<Integer> al=new ArrayList<Integer>();

for(int i=1;i*i <= n;i++)

return kIntegerSquaresUtil(n,al);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this will work with no constant space and linear time.

``````public static int MinSquare( int n ){
int curr =(int)Math.sqrt(n);
int count =1;

while (n!=0 || n!=1){
if ((curr*curr) == n ){
return count+1;
}
else if(curr*curr < n){
n=n-(curr*curr);
}
else{
if (curr != 1){
curr--;
}
n=n-(curr*curr);
count++;
}
}
return count;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int MinSquaresOfNumbers(int N)
{
vector<int> D(N + 1, INT_MAX);

D[0] = 0;
D[1] = 1;

for (int i = 2; i <= N; ++i)
{
int Min = INT_MAX;

D[i] = 1;

for (int K = (int)std::sqrt(i); K >= 1; --K)
{
int TempMin = D[K * K] + D[i - (K * K)];

if (TempMin < Min)
{
Min = TempMin;
}
}

D[i] = Min;
}

return (D[N]);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int MinSquaresOfNumbers(int N)
{
vector<int> D(N + 1, INT_MAX);

D[0] = 0;
D[1] = 1;

for (int i = 2; i <= N; ++i)
{
int Min = INT_MAX;

D[i] = 1;

for (int K = (int)std::sqrt(i); K >= 1; --K)
{
int TempMin = D[K * K] + D[i - (K * K)];

if (TempMin < Min)
{
Min = TempMin;
}
}

D[i] = Min;
}

return (D[N]);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Dynamic Programming solution in java:

``````public static int find(int N){

int[] tmp = new int[N+1];
tmp[0] = 0;
for(int i=1; i< N+1; i++){
int count = 2;
int min = tmp[i-1]+1;
while(i-Math.pow(count, 2) > -1){
min = Math.min(tmp[(int) (i-Math.pow(count, 2))]+1, min);
count++;
}
tmp[i] = min;
}
return tmp[N];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int findMin(int n){
int min = (int)Math.sqrt(n);
int[] dp = new int[n+1];
Arrays.fill(dp, n);
dp[0] = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j*j <= i; j++){
dp[i] = Math.min(dp[i],dp[i-j*j] + 1);
}
}
return dp[n];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

You are given a positive integer number N. Return the minimum number K, such that N can be represented as K integer squares.
Examples:
9 --> 1 (9 = 3^2)
8 --> 2 (8 = 4^2 + 4^2)
15 --> 4 (15 = 3^2 + 2^2 + 1^2 + 1^2)
First reach a solution without any assumptions, then you can improve it using this mathematical lemma: For any positive integer N, there is at least one representation of N as 4 or less squares.

The interviewer might be asking for minimal count.
72 (8,8)

This is the program with recursion

// SquareNumber.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <math.h>
#include <climits>
#include <vector>

int min_count=INT_MAX;
long long Steps = 0;
std::vector<int> min_stack;
std::vector<int> temp_stack;

int GetSquareCount(float num,int count)
{
Steps++;
if(num<0)
return 0;
if(num==0)
{
if(min_count> count)
{
min_count=count;
min_stack=temp_stack;
}
//return count;
}
/*for(int index=1;index<=sqrt(num);index++)
{
num=num-(index*index);
GetSquareCount(num,++count);

}*/
for(int index=sqrt(num);index>0;index--)
//for(int index=1;index<=sqrt(num);index++)
{
if(index==6)
{
int flag=1;
}
//num=num-(index*index);
if(count<min_count)
{
temp_stack.push_back(index);
GetSquareCount(num-(index*index),count+1);
temp_stack.pop_back();
}

}
return min_count;
}
int _tmain(int argc, _TCHAR* argv[])
{
int count=0;
float num=2522;
min_count=3;
int Count=GetSquareCount(num,count);
printf("min:%d Steps:%lld\n",min_count, Steps);
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

dp

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Looks like a variant of the coin change problem.
Here's a DP solution -:

``````#define INF 99999

int table[100000];

void init()
{
int i;
for(i=0; i<100000; i++)
{
table[i]=-1;
}
}

int minsquares(long long int n)
{
if(n<0)
return INF;
if(n==0)
return 0;

if(table[n]!=-1)
{
return table[n];
}

int ans=INF;
for(int i=1; i*i<=n; i++)
{
ans=min(ans, minsquares(n-i*i));

}

table[n]=ans+1;
return table[n];
}``````

Comment hidden because of low score. Click to expand.
-1
of 3 vote

Aren't we supposed to use squareroot function ?
If not then we can implement our own.
Algo for current problem

``````minsquares(int N)
{
if(N==0 || N==1) return N;
int squareRoot = sqrt(N);
return 1+minsquares(N - squareRoot*squareRoot)
}``````

Comment hidden because of low score. Click to expand.
0

Very nice solution

Comment hidden because of low score. Click to expand.
1
of 1 vote

Does work for 12,,, this gives 4, but actual is 3

Comment hidden because of low score. Click to expand.
0

Agree. Nice solution!

Comment hidden because of low score. Click to expand.
0

I agree with "Chala", for 12 it produces 4, but the actual is 3

Comment hidden because of low score. Click to expand.
0

hmm nice findings.

``````minsquares(int N)
{
if(N==0 || N==1) return N;
int squareRoot = sqrt(N);
return Math.Min(1+minsquares(N - squareRoot*squareRoot), 1+minsquares(N - (squareRoot-1)*(squareRoot-1))
}``````

but there are more corner cases then we might have to take the DP way :)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This can be done by observing that in order to find the minimum number of squares, we have to first the maximum number whose square is less than or equal to the given number. If it is equal, we are done. If it is less, subtract from N the square of the number just found...and repeat the process....here is a c# code

``````static int MinimumNumberOfSquares(int n)
{
int count = 0;
for (int j = n; j > 0; )
{
int k = 1;
while (k*k <= j)
{
k++;
}
count++;
j = j - (k - 1) * (k - 1);
}
return count;
}``````

Comment hidden because of low score. Click to expand.
0

i'm afraid this is not correct, for 12 you will generate 4, while the correct answer is 3

Comment hidden because of low score. Click to expand.
-1
of 1 vote

my dp solution

``````public int find_dp (int n){
if (n == 0) return 1 ;
int [] dp = new int [n + 1] ;
double bound = Math.sqrt(n) ;
dp[0] = 0 ;
for (int i = 1 ; i <= n  ; ++i) {
dp[i] = Integer.MAX_VALUE ;
for (int j = 1 ; j <= bound ; ++j) {
if (i >= Math.pow(j, 2)) {
dp[i] = dp[i - (int)Math.pow(j, 2)] + 1 < dp[i] ? dp[i - (int)Math.pow(j, 2)] + 1 : dp[i] ;
}
}
}
return dp[n] ;``````

}

my recursive method

``````public int find (double d, int count){
if (d == 0) return count ;
if (d < 0) return 0 ; ;
int min = Integer.MAX_VALUE;
for (int i = 1 ; i <= Math.sqrt(d) ;++i) {
if (d >= Math.pow(i, 2)) {
int c = find (d - Math.pow(i, 2), count +  1);
min = Math.min(c, min) ;
}
}
return min ;``````

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````class squareRepresentation{

public static void main( String a[] ){
Scanner in;

in = new Scanner( System.in );
int n = in.nextInt();

int x = getSquares( n );
System.out.println( "total = "+ x );
}

public static int getSquares( int n ){
if( n == 0 )return 0 ;

int x = (int)Math.sqrt( (double)n );
System.out.print( x+"\t" );

int total = 0;

return 1+getSquares( n- x*x );
}
}``````

Comment hidden because of low score. Click to expand.
0

Doesnt work for 12

Comment hidden because of low score. Click to expand.
0

@Enkokow - for 12 i'm getting total = 4 ( ie. 3 ,1 ,1 ,1) as ans.

why is this wrong?

Comment hidden because of low score. Click to expand.
0

12 => 3 ( 2^2 + 2^2 + 2^2 )

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.