CareerCup

Similar to DP problem , Minimum number of coins needed to make a given some.
Here instead of coin you have to take perfect square.

It will be like -
if n = 20
coins = {1,4,9,16}

By using minimum number of above coins you have to make a sum = 20

I will post code in other comment.

The solution code in java is here -

public class MinimumCoin {

	public static int findMin(int[] prfct, int k) {

		int[] arr = new int[k + 1];
		arr[0] = 0;
		
		for (int i = 1; i < arr.length; i++) {
			arr[i] = Integer.MAX_VALUE;
			for (int j = 0; j < prfct.length; j++) {

				if (prfct[j] <= i) {
					int temp = arr[i - prfct[j]] + 1;
					arr[i] = arr[i] > temp ? temp : arr[i] ;

				}
			}
		}

	
		
		return arr[k];

	}
	
	public static int[] buildArray(int N) {
		int l = (int) Math.sqrt(N);
		int[] prfct = new int[l];
		
		//System.out.println(prfct.length);
		for(int i=1;i<=l;i++) {
			prfct[i-1] = i*i;
		}
		
		
		return prfct;
	}

	public static void main(String[] args) {
		int N = 20;
		int[] prfct = buildArray(N); // Build the perfect square array

		int output = findMin(prfct, N); // find  the minimum using Dynamic programming approach
		
		System.out.println(output);
	}

}

Dynamic programming question.
Let P(i, j) be the min number of sum of sq root numbers, where i ∈ [0, round(sqrt(N))], j ∈ [0, N]. P(i,j) = min(P[i-1, j], P[i, j-1] + 1)

Using Dynamic Programming

public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		scan.close();
		
		if (n <= 3) {
			System.out.println(n);
			return;
		}
		
		int sqrt = (int)Math.sqrt(n);
		if (sqrt*sqrt == n) {
			// Number itself is perfect sqr
			System.out.println(1);
			return;
		}
	
		
		int dp[] = new int[n+1];
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 3;
		
		for (int i = 4; i <= n; i++) {
			dp[i] = i;
			
			for (int j = 1; j <= (int)Math.sqrt(i); j++) {
				int temp = j*j;
				if (temp > n) {
					break;
				}
				dp[i] = Math.min(dp[i], 1+dp[i-temp]);
			}
		}
		
		System.out.println(dp[n]);

}}

public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		scan.close();
		
		if (n <= 3) {
			System.out.println(n);
			return;
		}
		
		int sqrt = (int)Math.sqrt(n);
		if (sqrt*sqrt == n) {
			// Number itself is perfect sqr
			System.out.println(1);
			return;
		}
	
		
		int dp[] = new int[n+1];
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 3;
		
		for (int i = 4; i <= n; i++) {
			dp[i] = i;
			
			for (int j = 1; j <= (int)Math.sqrt(i); j++) {
				int temp = j*j;
				if (temp > n) {
					break;
				}
				dp[i] = Math.min(dp[i], 1+dp[i-temp]);
			}
		}
		
		System.err.println(dp[n]);
		
	}

public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		scan.close();
		
		if (n <= 3) {
			System.out.println(n);
			return;
		}
		
		int sqrt = (int)Math.sqrt(n);
		if (sqrt*sqrt == n) {
			// Number itself is perfect sqr
			System.out.println(1);
			return;
		}
	
		
		int dp[] = new int[n+1];
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 3;
		
		for (int i = 4; i <= n; i++) {
			dp[i] = i;
			
			for (int j = 1; j <= (int)Math.sqrt(i); j++) {
				int temp = j*j;
				if (temp > n) {
					break;
				}
				dp[i] = Math.min(dp[i], 1+dp[i-temp]);
			}
		}
		System.err.println(dp[n]);

}

if the answer is only about the length of sum:

unsigned minsum(unsigned v) {
    if (v <= 1)
        return v;
    unsigned min = (unsigned)-1;
    for (unsigned i = 1; i*i <= v; i++) {
        unsigned cur = 1 + minsum(v-i*i);
        if (cur < min)
            min = cur;
    }
    return min;
}

public int numberOfMinSquareSum(int n)
	{
		int num = n;
		int sqrt=0, carry=0;
		
		if(num <= 3)
			return num;
		else
		{
			sqrt = (int) Math.sqrt(num);
			carry = num-(sqrt*sqrt);
			
			if(carry==0)
				return 1;
			else
				return numberOfMinSquareSum(carry)+1;
		}
	}

int number(int N)
    {
        if(N<=0)
        {
            return 0;
        }

        int numbers=0;
        while(N>0)
        {
            N=N-(int)(Math.Sqrt(N))*(int)(Math.Sqrt(N));
            numbers++;
        }

        return numbers;

}

-(int)minimumSquareRoot:(int) number {
int count = 0;
int num = number;
while (num > 0) {
int flor = floor(sqrt(num));
num = num - (flor*flor);
count += 1;
}
}

-(int)minimumSquareRoot:(int) number {
int count = 0;
int num = number;
while (num > 0) {
int flor = floor(sqrt(num));
num = num - (flor*flor);
count += 1;
}
}

def check(N):
    import math
    lk = []
    count = 0
    for i in range(N, 0, -1):
        if int(math.sqrt(i) + 0.5) ** 2 == i and sum(lk) + i <= N:
            lk.append(i)
            count += 1
            N = N - 1
    print lk
    print count

def check(N) {
import math
lk = []
count = 0
for i in range(N, 0, -1):
if int(math.sqrt(i) + 0.5) ** 2 == i and sum(lk) + i <= N:
lk.append(i)
count += 1
N = N - 1
print lk
print count
}

def check(N):
    import math
    lk = []
    count = 0
    for i in range(N, 0, -1):
        if int(math.sqrt(i) + 0.5) ** 2 == i and sum(lk) + i <= N:
            lk.append(i)
            count += 1
            N = N - 1
    print lk
    print count

import math
lk =[]
count = 0
for i in range(N, 0, -1){
if int(math.sqrt(i) + 0.5) ** 2 == i and sum(lk) + i <= N {
lk.append(i)
count += 1
N = N - 1
}
}

print lk
print count

import math
    lk =[]
    count = 0
    for i in range(N, 0, -1){
        if int(math.sqrt(i) + 0.5) ** 2 == i and sum(lk) + i <= N {
            lk.append(i)
            count += 1
            N = N - 1
        }
    }
        
    print lk
    print count

{{
import math
lk =[]
count = 0
for i in range(N, 0, -1){
if int(math.sqrt(i) + 0.5) ** 2 == i and sum(lk) + i <= N {
lk.append(i)
count += 1
N = N - 1
}
}

print lk
print count}}}

int newPerfect( int n)
{
vector<int> arr(n+1);
if(n <= 3)
return n;
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;
arr[3] = 3;
for(int i=4; i<= n; i++ )
{
int min = INT_MAX;
int max = floor(sqrt(i));
for (int j =1; j <= max; j++ )
{
int val = arr[i - (j * j)] + 1;
if ( val < min)
min = val;
}

arr[i] = min;
}

return arr[n];
}

int newPerfect( int n)
{
	vector<int> arr(n+1);
	if(n <= 3)
		return n;
	arr[0] = 0;	
	arr[1] = 1;
	arr[2] = 2;
	arr[3] = 3;
	for(int i=4; i<= n; i++ )
	{
		int min = 9999;
		int max = floor(sqrt(i));
		for (int j =1; j <= max; j++ )
		{
			int val = arr[i - (j * j)] + 1;
			if ( val < min)
				min = val;
		}
		
		arr[i] = min;
	}
	
	return arr[n];
}

def numSquares(n):
    if n < 2:
        return n
    lst = []
    i = 1
    while i * i <= n:
        lst.append( i * i )
        i += 1
    print(lst)
    cnt = 0
    toCheck = {n}
    while toCheck:
        cnt += 1
        temp = set()
        for x in toCheck:
            for y in lst:
                if x == y:
                    return cnt
                if x < y:
                    break
                temp.add(x-y)
        toCheck = temp
        print(toCheck)
    return cnt

numSquares(12)

I solve this problem by recursive function.
f(n) = min(1+f(n-root^2), n//(root-1)^2+f(n%(root-1)^2)
f(0...4) = 0...4

import math
import sys


def find_no_of_perfect_square(n):
    if n<0:
        return sys.maxsize
    if n<4:
        return n
    elif n==4:
        return 1
    
    root = int(math.sqrt(n))
    if root>=2:
        return min(
            1+find_no_of_perfect_square(n-pow(root, 2)),
            n//pow(root-1,2) + find_no_of_perfect_square(n%pow(root-1,2))
        )
    else:
        return n


if __name__=='__main__':
    data = [
            [5, 2],
            [7, 4],
            [12, 3],
            [20, 2],
            ]
    for d in data:
        print('the least no of perfect square for', d[0], 'is', find_no_of_perfect_square(d[0]), 'expected', d[1])

static int getMinSquares(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 = Math.min(res, 1 + getMinSquares(n - temp));
}
return res;
}

fun sumOfPerfectSquares(target: Int) : Int {
    var targetCache = target-1
    var sum = target
    var count = 0
    while(targetCache > 0){
        if(isPerfectSquare(targetCache)){
            if(sum-targetCache == 0){
                // zero
                count++
                break
            } else if(sum-targetCache < 0) {
                // negative
                targetCache--
            } else {
                // positive
                count++
                sum -= targetCache
            }
        } else {
            targetCache--
        }
    }
    return count
}

fun isPerfectSquare(num : Int) : Boolean {
    val lastDigit = num%10
    val sumOfDigits = sumOfDigits(num)
    if (endsWithPerfectSum(lastDigit) && addsUpToPerfectSum(sumOfDigits)){
        return true
    }
    return false
}

fun endsWithPerfectSum(num: Int) =
        num == 0 || num == 1 || num == 4 || num == 5 || num == 6|| num == 9

fun addsUpToPerfectSum(num: Int) =
        num == 1 || num == 4 || num == 7 || num == 9

fun sumOfDigits(num: Int) : Int {
    var sum = 0
    var numCache = num
    while(numCache != 0){
        sum += numCache%10
        numCache = numCache/10
    }
    return sum
}

// k√k 0-1 knapsack
int solve(int k) {
int dp[k + 1];
dp[0] = 0;

for (int i = 1; i <= k; ++i) {
dp[i] = i;
for (int j = 1; j <= sqrt(i); ++j) {
dp[i] = min(dp[i], 1 + dp[i - j * j]);
}
}

return dp[k];
}

// k√k 0-1 knapsack
int solve(int k) {
  int dp[k + 1];
  dp[0] = 0;

  for (int i = 1; i <= k; ++i) {
    dp[i] = i;
    for (int j = 1; j <= sqrt(i); ++j) {
      dp[i] = min(dp[i], 1 + dp[i - j * j]);
    }
  }

  return dp[k];
}

public static void squareSum(int n){
    ArrayList<Integer> sqList = new ArrayList<Integer>();
    sqrtmeth(n);
  }
    public static void sqrtmeth(int k){

    int fstsq = (int) Math.sqrt(k);
    int temp = k - (fstsq * fstsq);
    if(temp==0){
   // sqList.add(fstsq * fstsq);

      //System.out.println(temp);
      System.out.println("Nums : " + fstsq + " Square is " + fstsq * fstsq);
    }
    else {
    sqrtmeth(temp);
    System.out.println("Nums : " + fstsq + " Square is " + fstsq * fstsq);

    }

    }

public static void squareSum(int n){
ArrayList<Integer> sqList = new ArrayList<Integer>();
sqrtmeth(n);
}
public static void sqrtmeth(int k){

int fstsq = (int) Math.sqrt(k);
int temp = k - (fstsq * fstsq);
if(temp==0){
// sqList.add(fstsq * fstsq);

//System.out.println(temp);
System.out.println("Nums : " + fstsq + " Square is " + fstsq * fstsq);
}
else {
sqrtmeth(temp);
System.out.println("Nums : " + fstsq + " Square is " + fstsq * fstsq);

}

}

public static void squareSum(int n){
    ArrayList<Integer> sqList = new ArrayList<Integer>();
    sqrtmeth(n); 
  }
    public static void sqrtmeth(int k){

    int fstsq = (int) Math.sqrt(k);
    int temp = k - (fstsq * fstsq);
    if(temp==0){
   // sqList.add(fstsq * fstsq);

      //System.out.println(temp);
      System.out.println("Nums : " + fstsq + " Square is " + fstsq * fstsq);
    }
    else {
    sqrtmeth(temp);
    System.out.println("Nums : " + fstsq + " Square is " + fstsq * fstsq);

    }

    }

Used recursion :

public static void squareSum(int n){
    ArrayList<Integer> sqList = new ArrayList<Integer>();
    sqrtmeth(n);
  }
    public static void sqrtmeth(int k){

    int fstsq = (int) Math.sqrt(k);
    int temp = k - (fstsq * fstsq);
    if(temp==0){
   // sqList.add(fstsq * fstsq);

      //System.out.println(temp);
      System.out.println("Nums : " + fstsq + " Square is " + fstsq * fstsq);
    }
    else {
    sqrtmeth(temp);
    System.out.println("Nums : " + fstsq + " Square is " + fstsq * fstsq);

    }

    }

Here is the solution for the problem :
{{
public static void main(String a[]) {
System.out.println(totalNoOfPerfectSquareRequiredToSum(10010000));
}

public static int totalNoOfPerfectSquareRequiredToSum(int k) {

int sqrt = (int) Math.sqrt(k);
int temp = k - (sqrt * sqrt);
if (temp == 0) {
return 1;
} else {
return 1 + totalNoOfPerfectSquareRequiredToSum(temp);
}

}}}

public static void main(String a[]) {
		System.out.println(totalNoOfPerfectSquareRequiredToSum(10010000));
	}

	public static int totalNoOfPerfectSquareRequiredToSum(int k) {

		int sqrt = (int) Math.sqrt(k);
		int temp = k - (sqrt * sqrt);
		if (temp == 0) {
			return 1;
		} else {
			return 1 + totalNoOfPerfectSquareRequiredToSum(temp);
		}

	}

public static void main(String args[]) throws Exception {
		System.out.println(minSumOfSquares(37));
	}

	public static int minSumOfSquares(int N) {
		int arr[] = new int[N + 1];
		Arrays.fill(arr, Integer.MAX_VALUE);
		arr[0] = 0;
		arr[1] = 1;
		arr[2] = 2;
		for (int i = 3; i <= N; i++) {
			double sqrt = Math.sqrt(i);
			int x = (int) sqrt;
			if (Math.pow(sqrt, 2) == Math.pow(x, 2)) {
				arr[i] = 1;
				continue;
			}
			for (int j = 1; j <= Math.sqrt(i); j++) {
				arr[i] = Math.min(arr[i], arr[(int) (i - Math.pow(j, 2))] + arr[(int) Math.pow(j, 2)]);
			}
		}
		System.out.println(Arrays.toString(arr));
		return arr[N];
	}