Finding the number of perfect squares in an array

Question

I am posting here for feedback about the code that I wrote to count the number of perfect squares in an array.

var arr = Array(4...17)
var count = 0
for i in arr{
 if Double(i).squareRoot().rounded() == Double(i).squareRoot(){
 count += 1
 }
}
print(count)

The result from the code is as expected. However, is this the "correct" way of doing? Or is there a "better" way of doing it? I did a coding test from a tech recruiting website (platform) and although the result is as expected, but the website gave me 0% on the "correctness" criteria and 0% overall mark.

Answer 1

Mathematical correctness

The used approach is incorrect for very large numbers, here is an example:

let i = 4611686014132420400
print(Double(i).squareRoot().rounded() == Double(i).squareRoot())
// true 

The output is true, even if the number is not a perfect square: \$ \sqrt{4611686014132420400} \approx 2147483646.9999999513383954536814215918 \$.

The reason is that a Double (which is a 64-bit floating point number according to the IEEE 754 standard) has only 53 bits for the "significand", therefore precision is lost in the conversion Double(i).

It also fails for negative numbers:

let i = -16
print(Double(i).squareRoot().rounded() == Double(i).squareRoot())
// false

because (-16.0).squareRoot() is NaN ("not a number").

But for non-negative numbers below \$ 2^{52} \,ドル your approach should be correct.

Swiftyness

arr is not mutated, therefore it should be a constant (with let):

let arr = Array(4...17)

But actually it is not needed to create an array with all numbers in the given range. You can iterate over a range directly:

let range = 4...17
for i in range { ... }

Even better, move the calculation into a separate function:

func numberOfPerfectSquares(in range: CountableClosedRange<Int>) -> Int {
 var count = 0
 for i in range {
 if Double(i).squareRoot().rounded() == Double(i).squareRoot(){
 count += 1
 }
 }
 return count
}
print(numberOfPerfectSquares(in: 4...17))

That allows you to add test cases, for example:

assert(numberOfPerfectSquares(in: 0...0) == 1)
assert(numberOfPerfectSquares(in: 100...10_000) == 91)
assert(numberOfPerfectSquares(in: 101...10_000) == 90)
assert(numberOfPerfectSquares(in: 101...9_999) == 89)
// ...
// More test cases if negative input is allowed:
assert(numberOfPerfectSquares(in: -10...10) == 9)
assert(numberOfPerfectSquares(in: -10_000...-100) == 91)
// ...

This is extremely useful to check the correctness if you changed the implementation.

Performance

Poor. Your code checks every number in the range if it is a perfect square or not. It is far more efficient to iterate over the possible square roots:

func numberOfPerfectSquares(in range: CountableClosedRange<Int>) -> Int {
 var count = 0
 var i = Int(Double(range.lowerBound).squareRoot())
 while i * i < range.lowerBound {
 i += 1
 }
 while i * i <= range.upperBound {
 count += 1
 i += 1
 }
 return count
}

This is already much faster, but you don't need a loop at all! It suffices to compute the number of perfect squares below the lower resp. upper bound, and return the difference:

func numberOfPerfectSquares(in range: CountableClosedRange<Int>) -> Int {
 // Number of perfect squares < lower bound:
 let lo = range.lowerBound == 0 ? 0 : Int(Double(range.lowerBound - 1).squareRoot()) + 1
 // Number of perfect squares <= upper bound:
 let hi = Int(Double(range.upperBound).squareRoot()) + 1
 return hi - lo
}

Note that this still does not work for negative numbers and numbers above \$ 2^{52} \$ due to the rounding errors. For the latter problem, see Computing the integer square root of large numbers.

• boidkan: Martin I want to be like you when I grow up :P
• Gamz Rs: thank you so much for the feedback. There are more things to learn for me. I hope i can get to where you are Martin

Answer 2

You are not using the Swift array methods (map, filter, ...)

let arr = Array(4...17)
let result= arr.filter{0ドル.squareRoot().rounded == 0ドル.squareRoot()}.count
print(result)

• Toby Speight: Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit it to explain your reasoning (how your solution works and how it improves upon the original) so that everyone can learn from your thought process.