• 5

Country: United States
Interview Type: In-Person

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

Dynamic programming..

``````int num_squares(int n){
int table[n+1];
int max = floor(sqrt(n));
int squared;

for (int i=0; i<=n; i++){
table[i] = i;
}
for (int i=2; i<=max; i++){
for (int j=0; j<=n; j++){
squared = pow(i,2);
if (squared <= j)
table[j] = min(table[j], table[j-squared]+1);
}
}
return table[n];
}``````

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

Can you please explain above algorithm?

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

tested with 13 and it gives 1 do you get the same result ?

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

This is what I get for n=1,...,19 using the code.
1 :1
2 :2
3 :3
4 :1
5 :2
6 :3
7 :4
8 :2
9 :1
10 :2
11 :3
12 :3
13 :2
14 :3
15 :4
16 :1
17 :2
18 :2
19 :3

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

I was mistaking one thing here, your results are right I'm getting the same now

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

Your solution looks good, only thing I would change is switch the squared = pow(i,2); to outside the for j loop, to avoid recalculating this value if not needed:

for (int i=2; i<=max; i++){
squared = pow(i,2);
for (int j=0; j<=n; j++){
if (squared <= j)
table[j] = min(table[j], table[j-squared]+1);
}
}

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

Possible optimizations:

// Perfect square will always be formed with exactly 1 square
// This is quickly checked with bit manipulation (ie. (j & j-1) == 0)
If j is a perfect square, set table[j] = 1, and break;

// Non-perfect square can only be at min formed from 2 squares
If j is not a perfect square and table[j] == 2, break;

These optimizations work best if your loop orders are swapped.

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

basically recurrence relation should be written with a possible explanation but @anonymous doesn't get it.
recurrence relation:
let f(n) be the least number of square which sum up to the given number "x".
f(n) = min(f(n), f(n-p)+1) where p can go up to max of sqrt(n).
so f(3) = min(f(3), f(3-1)+1)
f(3) = min(f(3), f(2) + 1)
where f(2) is 2
so f(3) = 3
we can calculate the value of any other 'n' with this recurrence relation.

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

imagine the perfect squares to be coins... Now, you have an amount and you need to get minimum possible coins needed to get the amount. That's a dynamic programming algorithm right...? This is a slight modification of that algorithm itself

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

imagine the perfect squares to be coins... Now, you have an amount and you need to get minimum possible coins needed to get the amount. That's a dynamic programming algorithm right...? This is a slight modification of that algorithm itself

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

Could you please explain the code ?

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

@OP: It looks like you're assuming 0 is a perfect square because in your sample output, n=4 -> 1 (4 + 0); n=16 -> 1 (16 + 0).

Is 0 actually considered a perfect square though?

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

``````// Dynamic Programming
using System.IO;
using System;

class Program
{
static void Main()
{
Console.WriteLine("Hello, World!");
int val = 12;
int[] table = new int[val+1];
table[0] = 0;

for ( int i=1; i<=val; i++){
int maxsqrt = (int) Math.Sqrt(i);
int localmin = i;
for (int j=1; j<=maxsqrt; j++){
if ( table[i-j*j] < localmin) {
localmin = table[i-j*j];
}
}
table[i] = localmin + 1;
}

Console.WriteLine("Min Val:"+ table[val]);
}
}``````

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

dont you mean "return 3" in the second example?

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

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

Bruteforce

``````def num_squares(n):
max = int(n**.5)
mincount = None
for r in range(max,0,-1):
z = n
p = r
count = 0
temp = []
while z > 0:
sq = p**2
if z - sq < 0:
p -= 1
continue
else:
z -= sq
count += 1
temp.append(p)
if mincount and count > mincount:
break

if z == 0:
if not mincount or count < mincount:
mincount = count

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

Greedy approach should work. Find the largest perfect square number s that is <= n. Apply the same to the difference (n - s). We can find s by taking square root of n as a float, and then truncating the result downward to the nearest integer.

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

I think this method gives a wrong answer for n=12

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

Greedy approach will not solve this problem

n=12 (3^2+1^2+1^2+1^2) takes 4 summation

Problem should be solved by using dynamic programming.

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

``````public static void main(String[] args){
int n = 12;
System.out.println("Ans: "+findSolution(n,0));
}

private static int  findSolution(int n, int count){
int sqrt = (int) Math.sqrt(n);
if((n!=0) && (sqrt*sqrt <= n)){
System.out.print(sqrt+" ");
count++;
count = findSolution(n-(sqrt*sqrt),count);
}
return count;
}``````

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

This is wrong.
Your code returns 3, 1, 1, 1 (4 numbers) but lowest number of numbers needed to make 12 is 2, 2, 2 (3 numbers)

Greedy solution doesn't work in this case.

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

``````int leastSquares_helper(int n, int max, unordered_map<int, int>* myMap) {
unordered_map<int,int>::const_iterator got = myMap->find(n);
if(got != myMap->end()) {
return got->second;
}
int largest = (int)sqrt(n);
if((largest * largest) == n) {
myMap->insert(pair<int,int>(n, 1));
return 1;
}
if(largest > max) {
largest = max;
}
int best = INT_MAX;

while ((largest * largest) > (n/best)) {
best = min(leastSquares_helper(n - (largest * largest), largest, myMap) + 1, best);
largest--;
}
myMap->insert(pair<int,int>(n, best));
return best;
}

int leastSquares(int n) {
unordered_map<int, int>* myMap = new unordered_map<int, int>;
return leastSquares_helper(n, INT_MAX, myMap);
}

int main(){

cout<<leastSquares(12);

getchar();
return 0;``````

}

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

this is much faster than a simple dynamic programming approach.
for example, for n=12:
I take 9 out and try to calculate 3 -> 2 - > 1
next I take 4 out and try to calculate 8->4 done.

my map is much smaller and I only calculate leastSquares for the numbers I need for the answer.

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

I think the code in the top is the most optimized one. But you gave out a good explanation to study this problem. Thanks dude!

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

As stated above, the solution is a Dynamic Programming algorithm.

The opt for this looks like:

``````OPT(value, root):
if value - (root^2) == 0 return 1
if value - (root^2) < 0 return INF
else return 1 + min(OPT(value - (root^2), k) for all k <= root)``````

We return INF if less than 0 to prevent overshoots from being counted.
Use of memoization is also helpful, having a cache which maps combinations of (value, root) to their calculated values will greatly improve our runtime.

In python, a quick mock up of this looks like

``````INFIN = 999999

memo = {}

def count_sqr_vals(val):
max_root = int(pow(val, 0.5))
return min([rec_search(val, x) for x in range(max_root, 0, -1)])

def rec_search(val, curr):
if memo.get((val,curr)):
return memo.get((val,curr))
if val - (curr**2) < 0:
memo[(val,curr)] = INFIN
return INFIN
if val - (curr**2) == 0:
memo[(val,curr)] = 1
return 1
min_val = min([rec_search(val - (curr**2), x) for x in range(curr, 0, -1)])
memo[(val,curr)] = 1 + min_val
return 1 + min_val``````

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

Bruteforce

``````def num_squares(n):
max = int(n**.5)
mincount = None
for r in range(max,0,-1):
z = n
p = r
count = 0
temp = []
while z > 0:
sq = p**2
if z - sq < 0:
p -= 1
continue
else:
z -= sq
count += 1
temp.append(p)
if mincount and count > mincount:
break

if z == 0:
if not mincount or count < mincount:
mincount = count

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

``````void LeastSquares(int num, std::vector<int>& best, std::vector<int>& curSeq = std::vector<int>(), int cur = 0)
{
if (!cur)
cur = (int)sqrtf((float)num);
if (!num && (!best.size() || (curSeq.size() < best.size())))
{
best = curSeq;
return;
}
if (best.size() && curSeq.size() >= best.size())
return;
for (; cur > 0; cur--)
{
if (num >= cur*cur)
{
curSeq.push_back(cur*cur);
LeastSquares(num - cur*cur, best, curSeq, cur);
curSeq.pop_back();
}
}
}

void main()
{
int num;
while (1)
{
std::cout << "Enter num\n";
std::cin >> num;
std::vector<int> result;
LeastSquares(num, result);
std::cout << result.size() << ": (";
for (int i = 0; i < result.size(); i++)
std::cout << result[i] << ((i == result.size()-1) ? "" : " + ");
std::cout << ")\n";
}
}``````

output:

``````Enter num
12
3: (4 + 4 + 4)
Enter num
6
3: (4 + 1 + 1)
Enter num
66
3: (64 + 1 + 1)
Enter num
666
2: (441 + 225)
Enter num
6666
3: (6241 + 400 + 25)
Enter num
66666
3: (66049 + 361 + 256)``````

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

``````def least_perfect_sqr_num(n):
if n == 1:
return 1

sqrts = []
total = []
for num in reversed(range(2, n + 1)):
if not num % math.sqrt(num):
sqrts.append(num)

if not sqrts:
return n
else:
for sqrt_no in sqrts:
total.append(1 + least_perfect_sqr_num(n - sqrt_no))

return min(total)``````

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

dynamic programming

``````public int findMin (int d){
int to = (int) Math.sqrt(d) ;
int []f = new int[d + 1];
for (int i = 1 ; i <= d ; ++i) {
f[i] = i ;
for (int j = 1 ; j <= to ; ++j) {
if (i >= j * j) {
f[i] = f[i - j * j] + 1 < f[i] ? f[i - j * j] + 1 : f[i] ;
}
}
}
return f[d];
}``````

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

``````class CountSquares
{
public static boolean isSquare(int n)
{
return Math.ceil(Math.sqrt(n)) == Math.floor(Math.sqrt(n));
}

public static int countSquaresNaive(int n)
{
if (n <= 1) {
return n;
}

int minCount = Integer.MAX_VALUE;

for (int i=n; i>=1; i--) {
if (isSquare(i)) {
int c = 1 + countSquaresNaive(n - i);
if (c < minCount) {
minCount = c;
}
}
}

return minCount;
}

public static int countSquaresDP(int n)
{
if (n <= 1) {
return n;
}

int[] L = new int[n+1];
for (int i=0; i<L.length; i++) {
L[i] = 0;
}
L[0] = 0;
L[1] = 1;

for (int i=2; i<=n; i++) {
if (isSquare(i)) {
L[i] = 1;
} else {
int minCount = Integer.MAX_VALUE;
int k = i / 2;
for (int j=i-1; j>=k; j--) {
minCount = Math.min(minCount, L[j] + L[i-j]);
if (minCount <= 2) {
break;
}
}
L[i] = minCount;
}
}

return L[n];
}

public static void main(String[] args)
{
for (int i=0; i<=50; i++) {
int a = countSquaresNaive(i);
int b = countSquaresDP(i);
assert a == b;
System.out.println("countSquaresNaive("+i+") = "+a+", countSquaresDP("+i+") = "+b);
}
}
}``````

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

Based on BFS search

``````typedef std::pair<unsigned,unsigned> numDepth;
std::queue<numDepth> q;
hash_set<unsigned> visited;

bool perfectSqrt(unsigned n)
{
unsigned r = floor(sqrt(n));
return ( n == r*r);
}

unsigned minSqrtSum(unsigned n)
{
if  ( perfectSqrt(n) ) { return 1;}
q.push(std::make_pair(n,0));
assert(n >0);
while (true)
{
numDepth next = q.front();
q.pop();
unsigned r = floor(sqrt(next.first));
for (unsigned  k = r; k>0; --k)
{
unsigned m = n - k*k;
if (visited.count(m) } continue;
if ( perfectSqrt(m) ) return next.second+2;
q.push(std::make_pair(m,next.second+1));
visited.insert(m);
}
}
}``````

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

``````import java.util.*;

class Program2{
int[] min;

Program2(){
min = new int[13];
Arrays.fill(min, Integer.MAX_VALUE);
}
public void findMin(int n){
min[0] = 0;
for(int i=1 ; i<=n ; i++){
for(int j=1 ; j*j<=i ; j++){
min[i] = Math.min(min[i], min[i - j*j] + 1);
}
}
}

public static void main(String[] args){
Program2 obj = new Program2();

obj.findMin(12);
System.out.println("Min Value: " + obj.min[12]);
}
}``````

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

``````int number = 45345345;
int sum = 0;
//int numCont = 0;
List<Integer> nums = new ArrayList<Integer>();

int num1 = number;
while(sum < number) {
double n = Math.floor(Math.sqrt(num1));
int square = (int) (n*n);
sum += square;
if (sum == number) {
break;
} else {
num1 = number - sum;
}
}

System.out.println(nums);
System.out.println(nums.size());``````

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

Dynamic programming. Here's an iterative bottom-up approach using memoization:

``````import math

def perfect_squares(n):
squares = [x * x for x in range(1, int(math.floor(math.sqrt(n)) + 1))]
counts = [x for x in range(0, n+1)]

for i in range(1, n+1):
for j in squares:
counts[i] = min(counts[i], 1 + counts[i-j])

return counts[n]``````

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

``````int solve(int n){

int minimumSquares[100];
for(int i=0;i<=n;++i)
minimumSquares[i] = i; /// i = 1^2 + .... + 1^2

for(int i=1;i<=n;++i)
for(int j=1;j*j<=i;++j)
if( minimumSquares[i] > 1 + minimumSquares[i - j*j])
minimumSquares[i] = 1 + minimumSquares[i - j*j];
return minimumSquares[n];``````

}

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

Dynamic programming

The key fact is:
S[i] = min(S[i-1^2] +1, S[i-2^2] +1, + S[i-3^2] +1... )

I took the top-down approach but the bottom up approach works as well.

``````#python
import math

def nsquares(num, mem):
if num in mem:
return mem[num]

vals = [nsquares(num - (i * i), mem)+1 for i in range(1, int(math.sqrt(num)) + 1)]
mem[num] = min(vals)
return mem[num]

print nsquares(7, {0 : 0, 1 : 1} ) #3 --> 7-4 = 3; 3-1 = 2; 2-1 = 1; 1-1 = 0``````

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

``````int f(int n) {
if (n < 4} return n;
auto s1 = int(sqrt(n)), s0 = s1-1;
s1 *= s1; s0 *= s0;
return min(n/s1 + f(n%s1), 1 + f(n-s0));
}``````

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

``````public int numOfSquares(int n)
{
if(n==0) return 0;
int[] arr = new int[n];

int count = 1;
for(int i=0; i<n; i++)
{
if(isPerfectSquare(i+1))
count = 0;
count ++;
arr[i] = count;
}

int maxNum = (int)Math.sqrt(n);
for(int a= 0; a<n; a++)
{
for(int i=1; i<=maxNum; i++)
{
int squared = (int) Math.pow(i, 2);
if ( a + squared >= n)
break;
int curMin = arr[a + squared];
if(arr[a] + 1 < curMin)
{
arr[a + squared] = arr[a] + 1;
}
}
}

return arr[n-1];
}

private boolean isPerfectSquare(int num)
{
int sqrtInt = (int) Math.sqrt(num);
return sqrtInt*sqrtInt == num;
}``````

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

public int calculateSquares(int n)
{
if(n<0){return -1;}

HashMap<Integer, Integer> leastSquaredmap = new HashMap();
map.put(0,1);
map.put(1,1);
return calculateSquaresHelper(n, map);
}

public int calculateSquaresHelper(int n, HashMap<Integer, Integer> map)
{
if(map!=null && map.contains(n))
{
return map.get(n);
}

//number is a perfect square
if(Math.sqrt(n) % 1 ==0)
{
map.put(n,1);
}

int min = Math.INT_MAX;
for(int i=1; i<=n; i++)
{
int j=n-i;
int minI = calculateSquaresHelper(i,map);
int minJ = calculateSquaresHelper(j,map);
if(minI+minJ < min)
{
min = minI+minJ;
}
}
map.put(n, min);
return min;
}

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

``````int num_of_squares(int n) {
if (n == 0)
return 0;
if (n ==1)
return 1;
// find the floor of square root of n
int x = (int)Math.sqrt(n);
// find what is left in n after subtracting square of x
int rem = n - (int)Math.pow(x, 2);
// Answer would be square of x plus num_of_squares(rem)
return 1+num_of_squares(rem);
}``````

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

``````public static int num_of_squares(int n) {
if (n==0)
return 0;
if (n==1)
return 1;
int x = (int) Math.sqrt(n);
int rem = n - (int)Math.pow(x, 2);
return 1+num_of_squares(rem);
}``````

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

public static int num_of_squares(int n) {
if (n==0)
return 0;
if (n==1)
return 1;
int x = (int) Math.sqrt(n);
int rem = n - (int)Math.pow(x, 2);
return 1+num_of_squares(rem);
}

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

``````public static int num_of_squares(int n) {
if (n==0)
return 0;
if (n==1)
return 1;
int x = (int) Math.sqrt(n);
int rem = n - (int)Math.pow(x, 2);
return 1+num_of_squares(rem);``````

}

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

``int``

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

{9}

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

There is a duplicate question a while ago. The number is no more than 4.
Follow this link to find out the previous question and one solution: cpluspluslearning-petert.blogspot.co.uk/2015/02/dynamic-programming-minimize-number-of.html.

A dynamic solution is provided as well.

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

what about tweak the question a little bit. The number is a total. In you hands, you have some coins and each coin values at 1, 4, 9, 16, 25 ... n^2 that less than the number. Try to use the least amount of coin to sum up your total.

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

what about tweak the question a little bit. The number is a total. In you hands, you have some coins and each coin values at 1, 4, 9, 16, 25 ... n^2 that less than the number. Try to use the least amount of coin to sum up your total.

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

check my explanation and solution:
allenlipeng47.com/PersonalPage/index/view/164/nkey

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

Using dynamic programming with recursion.

``````int min = Integer.MAX_VALUE ;

public void squareSum(int rem, int numsq) {
if( rem == 0 ) {
if( numsq < min )
min = numsq;
}
else if( rem > 0 ) {
for( int i=1; i <= Math.sqrt(rem); i++) {
squareSum( rem-(int)Math.pow(i,2), numsq+1);
}
}
}``````

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

``````#include<iostream>
using namespace std;

bool isSquare(int num, int& whose)
{
int i=2;
if(num==1)
{
whose = 1;
return true;
}
while(true)
{
if(i*i == num)
{
whose = i;
return true;
}
else if(i*i  > num)
{
return false;
}
i++;
}
}

int main()
{
int num;
cout<<"  Get Number :- ";
cin>>num;

int minTill = num;
int minV = 0;
int count;
int x = 0;
if(isSquare(num, x))
{
minV = 1;
minTill = 1;
}
if(num==3)
{
minV = 3;
minTill = 1;
}

while(minTill > 2)
{
bool check = false;
count = 0;
int diff = num;
int sum = 0;

for(int i=num;i>0;i--)
{
int t = 0;
if(isSquare(i, t))
{
if(minTill == t && check)
{
sum += t*t;
i = num-sum;
diff = diff-t*t;
count++;
}
else if(t==1)
{
count = count+diff;
i = 0;
}
else if(t<minTill)
{
if(!check)
{
minTill = t;
check = true;
}
sum += t*t;
i = num-sum;
diff = diff-t*t;
count++;
}
if(i==4 || i == 1)
{
count++;
i = 0;
}
}
if(i==0)
{
diff = num;
sum = 0;
check = false;
}
}
if(count == 2)
{
minV = 2;
break;
}
if(!minV)
minV = count;
else if(minV > count && !check)
minV = count;
cout<<endl<<endl;
}
cout<<"  Result is :- "<<minV<<endl;
return 0;
}``````

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

``````import math

table = {}

def perfect_square(number):
if number == 0:
return 0

sqrt = int(math.sqrt(number))
minimal = 100

for i in xrange(1, sqrt + 1):
calc = pow(i, i)
if number - calc >= 0:
if (number - calc) not in table:
table[number - calc] = perfect_square(number - calc) + 1

if table[number - calc] < minimal:
minimal = table[number - calc]

return minimal
print perfect_square(100)``````

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

``````public class SquareSumSvc
{
public static int findNumSquareTerms(int n)throws InvalidInputException
{
if(n<0)
{
throw new InvalidInputException();
}
int[] sumTermCounts=new int[n+1];
for(int i=0;i<=n;i++)
{
int sqrProd=i*i;
if(sqrProd<=n)
{
sumTermCounts[sqrProd]=1;//if i is a perfect square we only need 1 term.
}else
{
for(int j=0;j*j<=i;j++)
{
sumTermCounts[i]=Math.min(sumTermCounts[i],(sumTermCounts[j*j]+sumTermCounts[i-(j*j)]));
}
}
}
return sumTermCounts[n];
}
public static void main(String[] args)
{
int n=5;//expecting 2.
System.out.println(assertEquals(2,findNumSquareTerms(n,2)));
n=6;//expecting 3.
System.out.println(assertEquals(2,findNumSquareTerms(n,3)));

}
}``````

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

``````bool sqrtTry(double number, vector<double> v, int tries) {
if (tries == 1) {
if (floor(sqrt(number)) == ceil(sqrt(number))) {
v.push_back(sqrt(number));
for (int i = 0; i < v.size(); i++)
cout << v[i] << " ";
cout << endl;
return true;
}
return false;
}
else {
for (int i = 1; i <= number; i++) {
if (number - i * i > 0) {
vector<double> cpy = v;
cpy.push_back(i);
if (sqrtTry(number - i * i, cpy, tries - 1))
return true;
}
}
return false;
}
}
uint32_t _tmain()
{
vector<double> v;
bool succes = false;
int tries = 1;
while (!succes){
succes = sqrtTry(61, v, tries);
tries++;
}
return 0;
}``````

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

``````//Lagrange's four-square theorem (Bachet's conjecture)

int numSquares(int n) {
int root = sqrt(n);
if(root*root==n)
return 1;   //1 case handeled
while(n%4==0)
n/=4;
if(n%8==7)  //Thanks to Legendre 1798
return 4;   //Four case handeled
int i = root;
while(i*i>0){
int residue = n-(i*i);
int residue_root = sqrt(residue);
if(residue_root*residue_root == residue)
return 2;
i--;
}
return 3;
}``````

}

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

``````//Lagrange's four-square theorem (Bachet's conjecture)

int numSquares(int n) {
int root = sqrt(n);
if(root*root==n)
return 1;   //1 case handeled
while(n%4==0)
n/=4;
if(n%8==7)  //Thanks to Legendre 1798
return 4;   //Four case handeled
int i = root;
while(i*i>0){
int residue = n-(i*i);
int residue_root = sqrt(residue);
if(residue_root*residue_root == residue)
return 2;
i--;
}
return 3;``````

}

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

//Lagrange's four-square theorem (Bachet's conjecture)

int numSquares(int n) {
int root = sqrt(n);
if(root*root==n)
return 1; //1 case handeled
while(n%4==0)
n/=4;
if(n%8==7) //Thanks to Legendre 1798
return 4; //Four case handeled
int i = root;
while(i*i>0){
int residue = n-(i*i);
int residue_root = sqrt(residue);
if(residue_root*residue_root == residue)
return 2;
i--;
}
return 3;
}

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

``````//Lagrange's four-square theorem (Bachet's conjecture)

int numSquares(int n) {
int root = sqrt(n);
if(root*root==n)
return 1;   //1 case handeled
while(n%4==0)
n/=4;
if(n%8==7)  //Thanks to Legendre 1798
return 4;   //Four case handeled
int i = root;
while(i*i>0){
int residue = n-(i*i);
int residue_root = sqrt(residue);
if(residue_root*residue_root == residue)
return 2;
i--;
}
return 3;
}``````

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

``````//Lagrange's four-square theorem (Bachet's conjecture)

int numSquares(int n) {
int root = sqrt(n);
if(root*root==n)
return 1;   //1 case handeled
while(n%4==0)
n/=4;
if(n%8==7)  //Thanks to Legendre 1798
return 4;   //Four case handeled
int i = root;
while(i*i>0){
int residue = n-(i*i);
int residue_root = sqrt(residue);
if(residue_root*residue_root == residue)
return 2;
i--;
}
return 3;
}``````

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

``````//Lagrange's four-square theorem (Bachet's conjecture)

int numSquares(int n) {
int root = sqrt(n);
if(root*root==n)
return 1;   //1 case handeled
while(n%4==0)
n/=4;
if(n%8==7)  //Thanks to Legendre 1798
return 4;   //Four case handeled
int i = root;
while(i*i>0){
int residue = n-(i*i);
int residue_root = sqrt(residue);
if(residue_root*residue_root == residue)
return 2;
i--;
}
return 3;
}``````

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

#include<stdio.h>
#include<math.h>
int A[10000]={0};
int MinSquare(int n)
{
int max=999999;
if(n==0)
{
return 0;
}
int i;
if(A[n]==0)
{
for(i=1;i<=sqrt(n);i++)
{
int x=n-(i*i);
if(x<0)
{
break;
}

int y=1+MinSquare(x);
if(y<=max)
{
max=y;
}
}
A[n]=max;
}
else
{
max=A[n];
}
return max;
}

int main()
{
printf("%d",MinSquare(24));
return 0;
}

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

#include<stdio.h>
#include<math.h>
int A[10000]={0};
int MinSquare(int n)
{
int max=999999;
if(n==0)
{
return 0;
}
int i;
if(A[n]==0)
{
for(i=1;i<=sqrt(n);i++)
{
int x=n-(i*i);
if(x<0)
{
break;
}

int y=1+MinSquare(x);
if(y<=max)
{
max=y;
}
}
A[n]=max;
}
else
{
max=A[n];
}
return max;
}

int main()
{
printf("%d",MinSquare(24));
return 0;
}

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

``````#include<stdio.h>
#include<math.h>
int A[10000]={0};
int MinSquare(int n)
{
int max=999999;
if(n==0)
{
return 0;
}
int i;
if(A[n]==0)
{
for(i=1;i<=sqrt(n);i++)
{
int x=n-(i*i);
if(x<0)
{
break;
}

int y=1+MinSquare(x);
if(y<=max)
{
max=y;
}
}
A[n]=max;
}
else
{
max=A[n];
}
return max;
}

int main()
{
printf("%d",MinSquare(24));
return 0;
}``````

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

#include<stdio.h>
#include<math.h>
int A[10000]={0};
int MinSquare(int n)
{
int max=999999;
if(n==0)
{
return 0;
}
int i;
if(A[n]==0)
{
for(i=1;i<=sqrt(n);i++)
{
int x=n-(i*i);
if(x<0)
{
break;
}

int y=1+MinSquare(x);
if(y<=max)
{
max=y;
}
}
A[n]=max;
}
else
{
max=A[n];
}
return max;
}

int main()
{
printf("%d",MinSquare(24));
return 0;
}

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

#include<stdio.h>
#include<math.h>
int A[10000]={0};
int MinSquare(int n)
{
int max=999999;
if(n==0)
{
return 0;
}
int i;
if(A[n]==0)
{
for(i=1;i<=sqrt(n);i++)
{
int x=n-(i*i);
if(x<0)
{
break;
}

int y=1+MinSquare(x);
if(y<=max)
{
max=y;
}
}
A[n]=max;
}
else
{
max=A[n];
}
return max;
}

int main()
{
printf("%d",MinSquare(24));
return 0;
}

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

Its edit of 1-0 Knapsack problem

Formula -

if j < sql[i - 1]
dp[i, j] = dp[i -1, j]
elif sq[i - 1] % j == 0
dp[i, j] = sq[i - 1] / j
else
dp[i, j] = min(dp[i - 1, j], (sq[i - 1] / j) + dp[i - 1, j - sq[i - 1] % j]

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

``````def getmin(n):
dp = dict()
dp[0] = 0
dp[1] = 1
dp[2] = 2
dp[3] = 3
for i in range(4,n+1):
dp[i] = i
for x in range(1,i+1):
tmp = x*x
if tmp > i:
break
else:
dp[i] = min(dp[i], 1+dp[i-tmp])
res = dp[n]
del dp
return res
print "Enter Number"
num = int(raw_input())
print getmin(num)``````

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

C++ solution:

``````#include <iostream>
#include <vector>
#include <cmath>
#include <string>

using uint = unsigned int;
using VectorUInts = std::vector<unsigned int>;

VectorUInts GetLeastPerfectSquares(uint n) {
if (n == 0) {
return VectorUInts{};
}

VectorUInts minSoFar;

bool hasMinBeenFound = false;

uint cachedStartValue = sqrt(n);
bool isFirstMainLoop = true;
while(!hasMinBeenFound && cachedStartValue > 0) {
uint currInt = n;
bool isFirstLoop = true;
VectorUInts squares;
while(currInt > 0) {
uint newVal = 0;
if (!isFirstMainLoop && isFirstLoop) {
newVal = cachedStartValue;
}
else {
newVal = static_cast<uint>(sqrt(static_cast<float>(currInt)));
}

if(isFirstLoop) {
cachedStartValue = (cachedStartValue - 1);
isFirstLoop = false;
}

newVal = newVal * newVal;

if (newVal > 0) {
squares.push_back(newVal);
}

currInt -= newVal;
}

if (squares.size() < minSoFar.size() || isFirstMainLoop)  {
minSoFar = std::move(squares);
isFirstMainLoop = false;
}
else {
hasMinBeenFound = true;
}

}

return minSoFar;
}

int main (int argc, char **argv) {
auto leastPerfectSquares = GetLeastPerfectSquares(std::stoul(argv[1]));

for (const auto &val : leastPerfectSquares) {
std::cout << val << "\n";
}

return 0;
}``````

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

Greedy approach should work? Find the largest square number s that's <= given number n. Then apply recursively to (n - s). Since 1 is a square number, we're guaranteed to be reach n.

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

Greedy does not work. 18 = 4^2 + 1^2 + 1^2 is the greedy solution.
But.. the optimal is 18 = 3^2 + 3^2.

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

Greedy solution would find, for the first example, a count of four:
12 = (3^2 + 1^2 + 1^2 + 1^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.