DEV Community

Pathipati Suresh Kumar
Pathipati Suresh Kumar

Posted on

Binary Gap of a Number

when ever I think of interview, this question always have a JamesBond entry in my mind.

Question:

Given a number, you need to convert it to binary format and then find the maximum no.of zero's between two 1's(binary gap)

Approach:

One among Many

  1. Convert the number to binary
  2. Have a loop and find the maximum no.of zero's b/w 1's

1. Convert to binary

1) Well this can be done using basic mathematics(My Approach)


2) Ruby has inbuilt function "to_s(< format >)" for Fixnum(Best, Clear and Easy)

2. Find the BinaryGap of the string

1) My approach was having a loop inside a loop, and iterate over the entire string/array and making it more complex. Yes, its horrible :) and we can do this in a better way.

2) Here, we will be checking the entire string. we decide what to do when 1's and 0's are encountered.

[Note]
FlagVariable is required only when we intentionally pass a binary string starting with zero.

Let me know, if this can be done differently ;)

Thanks for your time.

Top comments (2)

Collapse
 
baweaver profile image
Brandon Weaver

Enumerable in Ruby has a lot of handy methods you may enjoy. In this case we'll want String#chars, Enumerable#slice_when, Enumerable#max_by, and Array#size:

def binary_gap(string)
  string
    .chars
    .slice_when { |a, b| a != b }
    .max_by { |s| s[0] == '0' ? s.size : 0 }
    .size
end

Now commenting that out to explain what's going on:

def binary_gap(string)
  string
    # Get the characters of a string
    .chars
    # Slice them into groups when the next character isn't equal to the previous one
    .slice_when { |a, b| a != b }
    # Find the biggest group, but only if it's a group of 0s, return 0 for 1 to make it lesser
    .max_by { |s| s[0] == '0' ? s.size : 0 }
    # Then finally get the size of that largest group
    .size
end

each_char could probably be used here as well.

Collapse
 
sureshpathipati profile image
Pathipati Suresh Kumar

Agree!. Looks even better and understandable