868 Binary gap

Given a positive integer n, find and return the longest distance between any two adjacent 1's in the binary representation of n. If there are no two adjacent 1's, return 0.

Two 1's are adjacent if there are only 0's separating them (possibly no 0's). The distance between two 1's is the absolute difference between their bit positions. For example, the two 1's in "1001" have a distance of 3.

Example 1:

Example 2:

Example 3:

Constraints:

  • 1 <= n <= 109

Approach 1:

Using a list to store index position of 1's

Convert the number to the binary format . Then iterate over the binary string. If the value is 1 then add the index position to the list. After traversing the entire string. Calculate the required max distance using the list created.

Time : O(logn)

Space: O(logn)

Approach 2:

By storing previous position where a 1 is found

While on iteration on the binary string , we will store the indexes , where a ‘1' is found and when current position also is found to have a 1 , we will be calculating the distance, by the formula (prev -current), if this current distance is greater than maximum distance found so far, then we will have to update the maximum distance variable by the new distance.

Time : O(logn)

Space: O(1)

Approach 3:

The same solution above can be implemented in a different way by using it operation , rather than creating a binary string

Time : O(logn)

Space: O(1)

--

--

--

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

How Fever has speed-up e2e execution time by 16.5% using Cypress and Github Actions.

The Ultimate Guide to Joining Makers

Warning: The Dataset Is under Maintenance

Tableau Guide #3: Convex Hulls

A Linux Survey For Beginners

Linux For Beginners

The First Bouncing Ball Project

OOP(Object Oriented Programming)

Flame 1.0 is here!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Dhanarajappu

Dhanarajappu

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.

More from Medium

Tree Traversal Using Tail Recursion

Increasing Triplet Subsequence

What is Recursion and TCO?

Date/Time and Daylight saving for Programmers