## Salar

BAN USER
Comments (4)

Reputation 10

Page:

1

Comment hidden because of low score. Click to expand.

Comment hidden because of low score. Click to expand.

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

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

}

- Salar March 12, 2015Page:

1

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

- Salar May 14, 2017