Minimum number of squares whose sum equals to given number n - GeeksforGeeks

Minimum number of squares whose sum equals to given number n - GeeksforGeeks
A number can always be represented as a sum of squares of other numbers. Note that 1 is a square and we can always break a number as (1*1 + 1*1 + 1*1 + …). Given a number n, find the minimum number of squares that sum to X.

int getMinSquares(int n)

{

    // Create a dynamic programming table

    // to store sq

    int *dp = new int[n+1];

    // getMinSquares table for base case entries

    dp[0] = 0;

    dp[1] = 1;

    dp[2] = 2;

    dp[3] = 3;

    // getMinSquares rest of the table using recursive

    // formula

    for (int i = 4; i <= n; i++)

    {

        // max value is i as i can always be represented

        // as 1*1 + 1*1 + ...

        dp[i] = i;

        // Go through all smaller numbers to

        // to recursively find minimum

        for (int x = 1; x <= i; x++) {

            int temp = x*x;

            if (temp > i)

                break;

            else dp[i] = min(dp[i], 1+dp[i-temp]);

        }

    }

    // Store result and free dp[]

    int res = dp[n];

    delete [] dp;

    return res;

}

http://algorithms.tutorialhorizon.com/dynamic-programming-minimum-numbers-are-required-whose-square-sum-is-equal-to-a-given-number/

	public void solve(int n) { int options = (int) Math.sqrt(n);
	//solve using Dynamic programming
	System.out.println(solveUsingDP(n, options));
	}
	public int solveUsingDP(int n, int options) {
	int MN[] = new int[n+1]; // Minimum numbers required whose sum is = n
	MN[0] = 0; // if number is 0 the answer is 0.
	int[] NUM = new int[options+1];
	// solve in bottom up manner
	for (int number = 1; number <= n; number++) {
	// reset the NUM[] for new i
	for (int j = 0; j <= options; j++) {
	NUM[j] = 0;
	}
	// now try every option one by one and fill the solution in NUM[]
	for (int j = 1; j <= options; j++) {
	// check the criteria
	if (j * j <= number) {
	// select the number, add 1 to the solution of number-j*j
	NUM[j] = MN[number - j * j] + 1;
	}
	}
	//Now choose the optimal solution from NUM[]
	MN[number]=-1;
	for(int j=1;j<NUM.length;j++){
	if(NUM[j]>0 && (MN[number]==-1 || MN[number]>NUM[j])){
	MN[number]=NUM[j];
	}
	}
	}
	return MN[n];
	}

http://likemyblogger.blogspot.com/2015/08/mj-15-minimum-number-of-square-sum.html

1. find all the squares not greater than n and construct vec
2. follow the idea of Combination Sum [3] to find the minimum number of ways

    int getMinPartitions(int n){

        int m = sqrt(n);

        vector<int> vec(m);

        for(int i=1; i<=m; ++i){

            vec[i-1] = i*i;

        }

        int min_sz = INT_MAX;

        bt(vec, n, min_sz, m, 0, 0, 0);

        return min_sz;

    }

    void bt(vector<int> vec, int target, int &min_sz, int sz, int pos, int cur_sz, int sum){

        if(sum==target){

            min_sz = min(min_sz, cur_sz);

        }else if(pos<sz && sum<target && cur_sz<min_sz){

            for(int i=pos; i<sz; ++i){

                if(sum+vec[i]>target) return;

                bt(vec, target, min_sz, sz, i, cur_sz+1, sum+vec[i]);

            }

        }

    }

X. exponential

// Returns count of minimum squares that sum to n

int getMinSquares(unsigned int n)

{

    // base cases

    if (n <= 3)

        return n;

    // getMinSquares rest of the table using recursive

    // formula

    int res = n; // Maximum squares required is n (1*1 + 1*1 + ..)

    // Go through all smaller numbers

    // to recursively find minimum

    for (int x = 1; x <= n; x++)

    {

        int temp = x*x;

        if (temp > n)

            break;

        else

            res =  min(res, 1+getMinSquares(n - temp));

    }

    return res;

}

Read full article from Minimum number of squares whose sum equals to given number n - GeeksforGeeks