I recently had the chance to try Codility's algorithm training, and the very first one in the list is finding the longest binary gap of a given integer.
I tried to implement this in Swift, and after finishing it up, I looked at answers all over the internet. My approach is a bit different from what I have seen from others.
What is a Binary Gap?
A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.
For example, number 9 has binary representation
1001
and contains a binary gap of length 2. The number 529 has binary representation1000010001
and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation10100
and contains one binary gap of length 1. The number 15 has binary representation1111
and has no binary gaps. The number 32 has binary representation100000
and has no binary gaps.
The following is from the console which makes it easy to understand the implementation.
Binary String of "1041" is: "10000010001"
Position of 1's: [0, 6, 10]
The longest binary gap is 5
Basically what I am doing is:
- Iterating each binary character, and store the position/index of 1's in an array.
- As I am looping through, I find the binary gap between two 1's by subtracting the current index of
1
with previous index of1
, so that it gives me how many0
's are present in between them. I then decrement whatever value I get by 1 ('cause arrays...). - As I am looping through, I keep track of the longest binary gap in a variable.
The complexity is O(n), and I'd like to know if this approach is in any way efficient in terms of memory, or any scope of improvements with this? Thanks for your time.
Code:
public func getLongestBinaryGapFor(_ N : Int) -> Int {
var arrayOfIndexes:[Int] = []
let binaryString = String(N, radix:2)
print("Binary String of \"\(N)\" is: \"\(binaryString)\"")
var longestBinaryGap:Int = 0
var index = 0
for char in binaryString {
if char == "1" {
arrayOfIndexes.append(index)
let currentBinaryGap = getCurrentBinaryGapFor(arrayOfIndexes)
if arrayOfIndexes.count == 2 {
longestBinaryGap = currentBinaryGap
} else if index > 2 {
if currentBinaryGap > longestBinaryGap {
longestBinaryGap = currentBinaryGap
}
}
}
index += 1
}
print("Position of 1's: \(arrayOfIndexes)")
return longestBinaryGap
}
func getCurrentBinaryGapFor(_ array:[Int]) -> Int {
var currentBinaryGap = 0
if array.count >= 2 {
let currentPosition = array.count - 1
let previousPosition = currentPosition - 1
currentBinaryGap = array[currentPosition] - array[previousPosition] - 1
return currentBinaryGap
} else {
return currentBinaryGap
}
}