CareerCup

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;
}

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]

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;
        }

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));
	}
}

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];
		
	}


}

Simple recursive solution:

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

   int i = 1;

   int best_answer = n;

   int current_answer;

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

      if ( best_answer > 1 + current_answer )
      {
         best_answer = 1 + current_answer;
      }
      i++;
   }

   return best_answer;
}

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;
}

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];
}

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];
}

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];
}

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];
}

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;
}

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?

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.

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)

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)

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++)
			al.add(i*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.

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++)
			al.add(i*i);
		
		return kIntegerSquaresUtil(n,al);
	}

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++)
			al.add(i*i);
		
		return kIntegerSquaresUtil(n,al);
	}

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;
	}

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]);
}

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]);
}

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];
	}

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];
    }

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.
example 72 answer: 2
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;
}

dp

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];
}

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)
}

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;
        }

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 ;

}

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 );
        }
}