Skip to content

Instantly share code, notes, and snippets.

@austra
Last active December 14, 2017 21:23
Show Gist options
  • Save austra/a132be5a0e4bc75b365cb651d280b7bf to your computer and use it in GitHub Desktop.
Save austra/a132be5a0e4bc75b365cb651d280b7bf to your computer and use it in GitHub Desktop.
Largest Binary Gap
I read about this problem and thought I would try it. Later I found it is a question here too:
https://codility.com/programmers/lessons/1-iterations/binary_gap/
My first instinct was, "I know regex can do this, but I hate regex" (Which is also a good reason to get better at regex).
I couldn't quite hoop the syntax so I moved on. Here is what I came up with:
def max_binary_gap(n)
max_gap = 0
arr = n.to_s(2).chars
while arr.size > 2 do
next_index = arr.index("1")
break unless next_index
arr.delete_at next_index
next_index = arr.index("1")
break unless next_index
max_gap = next_index if next_index > max_gap
arr.slice!(0...next_index)
end
max_gap
end
I came back to the regex approach, found this pattern /1(0+)(?=1)/, which uses lookahead to find the gaps nicely.
I originally thought this would be much faster too.
max_binary_gap(n)
arr = n.to_s(2).scan(/1(0+)(?=1)/).flatten
arr.empty? ? 0 : arr.max.size
end
However, turns out they are about the same:
Benchmark.bmbm do |bm|
bm.report('array indexing') do
max_gap = 0
arr = n.to_s(2).chars
while arr.size > 2 do
next_index = arr.index("1")
break unless next_index
arr.delete_at next_index
next_index = arr.index("1")
break unless next_index
max_gap = next_index if next_index > max_gap
arr.slice!(0...next_index)
end
max_gap
1000000.times do
n = rand(2147483647)
max_binary_gap(n)
end
end
bm.report('regex') do
def max_binary_gap(n)
arr = n.to_s(2).scan(/1(0+)(?=1)/).flatten
arr.empty? ? 0 : arr.max.size
end
1000000.times do
n = rand(2147483647)
max_binary_gap(n)
end
end
end
array indexing 6.600000 0.000000 6.600000 ( 6.598933)
regex 6.770000 0.000000 6.770000 ( 6.775859)
describe "solution" do
def max_binary_gap(n)
max_gap = 0
arr = n.to_s(2).chars
while arr.size > 2 do
next_index = arr.index("1")
break unless next_index
arr.delete_at next_index
next_index = arr.index("1")
break unless next_index
max_gap = next_index if next_index > max_gap
arr.slice!(0...next_index)
end
max_gap
end
context "example1" do
it { expect(solution(1041)).to eq 5 }
end
context "example2" do
it { expect(solution(15)).to eq 0 }
end
context "extremes" do
it { expect(solution(1)).to eq 0 }
it { expect(solution(5)).to eq 1 }
it { expect(solution(2147483647)).to eq 0 }
end
context "trailing_zeroes" do
it { expect(solution(6)).to eq 0 }
it { expect(solution(328)).to eq 2 }
end
context "power_of_2" do
it { expect(solution(16)).to eq 0 }
it { expect(solution(1024)).to eq 0 }
end
context "simple1" do
it { expect(solution(9)).to eq 2 }
it { expect(solution(11)).to eq 1 }
end
context "simple2" do
it { expect(solution(19)).to eq 2 }
it { expect(solution(42)).to eq 1 }
end
context "simple3" do
it { expect(solution(1162)).to eq 3 }
it { expect(solution(5)).to eq 1 }
end
context "medium1" do
it { expect(solution(51712)).to eq 2 }
it { expect(solution(20)).to eq 1 }
end
context "medium2" do
it { expect(solution(561892)).to eq 3 }
it { expect(solution(9)).to eq 2 }
end
context "medium3" do
it { expect(solution(66561)).to eq 9 }
end
context "large1" do
it { expect(solution(6291457)).to eq 20 }
end
context "large2" do
it { expect(solution(74901729)).to eq 4 }
end
context "large3" do
it { expect(solution(805306369)).to eq 27 }
end
context "large4" do
it { expect(solution(1376796946)).to eq 5 }
end
context "large5" do
it { expect(solution(1073741825)).to eq 29 }
end
context "large6" do
it { expect(solution(1610612737)).to eq 28 }
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment