Good morning! Here's our prompt for today.
A perfect square is a number made by squaring a whole number.
Some examples include 1
, 4
, 9
, or 16
, and so on -- because they are the squared results of 1
, 2
, 3
, 4
, etc. For example:
SNIPPET
11^2 = 1
22^2 = 4
33^2 = 9
44^2 = 16
5...
However, 15
is not a perfect square, because the square root of 15
is not a whole or natural number.
Perfect Square | Factors |
---|---|
1 | 1 * 1 |
4 | 2 * 2 |
9 | 3 * 3 |
16 | 4 * 4 |
25 | 5 * 5 |
36 | 6 * 6 |
49 | 7 * 7 |
64 | 8 * 8 |
81 | 9 * 9 |
100 | 10 * 10 |
Given some positive integer n, write a method to return the fewest number of perfect square numbers which sum to n.
The follow examples should clarify further:
JAVASCRIPT
1var n = 28
2howManySquares(n);
3// 4
4// 16 + 4 + 4 + 4 = 28, so 4 numbers are required
On the other hand:
JAVASCRIPT
1var n = 16
2howManySquares(n);
3// 1
4// 16 itself is a perfect square
5// so only 1 perfect square is required
Constraints
n
<=10000
n
will always be non zero positive integer- Expected time complexity :
O(n*sqrt(n))
- Expected space complexity :
O(n)
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
30
var assert = require('assert');
​
function howManySquares(n) {
return n;
}
​
try {
assert.deepEqual(howManySquares(12), 3);
​
console.log('PASSED: ' + 'howManySquares(12) should return 3');
} catch (err) {
console.log(err);
}
​
try {
assert.deepEqual(howManySquares(1), 1);
​
console.log('PASSED: ' + 'howManySquares(1) should return 1');
} catch (err) {
console.log(err);
}
​
try {
assert.deepEqual(howManySquares(966), 3);
​
console.log('PASSED: ' + 'howManySquares(966) should return 3');
} catch (err) {
console.log(err);
}
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
Here's how we would solve this problem...
How do I use this guide?