'Solving Binary Gap using Recursion
I am trying to solve binary gap problem using recursion. It can be easily solved without recursion. But I want to solve this with recursion.The below program takes an integer as input and finds the binary gap.
Example:
input= 9, Binary form = 1001, Answer = 2
input=37, Binary form = 100101, Answer = 2
It finds the maximum number of zeros that occur between two 1's in the binary representation.
I want to solve this in O(logn). Right now, the below program simply counts the total number of zeros and gives output 3 instead of 2. How do I correct this to get the right output?
class BinaryGap {
public int solution(int N){
return solution(N, false, 0);
}
public int solution(int N, boolean prevFlag, int memo) {
if(N<2)
return 0;
int remainder = N%2 ;
if(prevFlag){
if(remainder == 0){
memo = 1 + solution(N/2, prevFlag, memo);
} else {
int newGap = solution(N/2, prevFlag, memo);
if(newGap > memo)
memo = newGap;
}
} else {
prevFlag = (remainder == 1);
return solution(N/2, prevFlag, 0);
}
return memo;
}
public static void main(String args[]){
BinaryGap obj = new BinaryGap();
System.out.println(obj.solution(37));
}
}
Solution 1:[1]
In Java 8, you can use stream to solve this:
static int calculateBinaryGap(int N) {
return Stream
.of(
// integer to binary string
Integer.toBinaryString(N)
// trim 0(s) at the end
.replaceAll("0+$", "")
// split string with 1(s)
.split("1+"))
// lambda expressions: use filter to keep not null elements
.filter(a -> a != null)
// method references: convert string to integer by using the
// length of string
.map(String::length)
// method references: find the largest number in the stream by
// using integer comparator
.max(Integer::compare)
// return 0 if nothing matches after the process
.orElse(0);
}
There is a good article about Streams: Processing Data with Java SE 8 Streams
Solution 2:[2]
As many people were facing problem in handling the trailing zeros condition of the solution. Below is my solution with 100% test cases passing.
class Solution {
public int solution(int N) {
// write your code in Java SE 8
return binaryGap(N,0,0,0);
}
public int binaryGap(int n, int counter, int max, int index){
if(n==0)
return max;
if(n%2==0 && index==0)
index=0;
else if(n%2==0)
counter ++;
else {
max = Math.max(counter, max);
index++;
counter =0;
}
n = n/2;
return binaryGap(n, counter, max, index);
}
}
Solution 3:[3]
My solution. 100% without recursion.
class Solution {
public int solution(int N) {
String binary = Integer.toString(N, 2);
int largestGap = 0;
for (int i = 1, gap = 0; i < binary.length(); i++) {
while (i < binary.length() && binary.charAt(i) == '0') {
i++;
gap++;
}
if (gap > largestGap && i < binary.length()) {
largestGap = gap;
}
gap = 0;
}
return largestGap;
}
}
Solution 4:[4]
We can split the binaryString with 1 as the delimiter
Eg: N=1041 BinaryString = 10000010001
When its split based on 1 as delimiter we get [, 00000, 000]
and then the subproblem becomes to find the array with largest length
private static int solution(int N) {
int gap = 0;
String binaryStr = Integer.toBinaryString(N);
String[] zeroArrays = binaryStr.split("1");
System.out.println(Arrays.toString(zeroArrays));
for(String zeroArray : zeroArrays) {
gap = zeroArray.length() > gap ? zeroArray.length() : gap;
}
return gap;
}
Solution 5:[5]
This answer is tested on coditilty and it has got 100% for performance and correctness.
Hope it will help someone.
public static int solution(int N) {
int binaryGap = 0;
String string = Integer.toBinaryString(N).replaceAll("0+$", "");
String[] words = string.split("1+");
Arrays.sort(words);
if(words.length != 0) {
binaryGap = words[words.length -1].length();
}
return binaryGap;
}
Solution 6:[6]
Ruby Solution (No recursion - 100% correctness in Codility):
`
def binary_gap(number)
remainder = []
while number > 0
remainder << number % 2
number = number / 2
end
binary_number = remainder.reverse.join('')
biggest_gap = 0
current_gap = 0
status ='stop'
binary_number.reverse.each_char do |char|
if char =='1'
status = 'start'
current_gap = 0
elsif char == '0' && status =='start'
current_gap +=1
end
if current_gap > biggest_gap
biggest_gap = current_gap
end
end
return biggest_gap
end
`
Solution 7:[7]
I think @saka1029 is almost there, just like @xuesheng said that solution will not work if the input for example are 2 = 010, 4 = 100, 6 = 110.
I would like to suggest do this below instead
static int solution(int n) {
return solution(n, 0, 0, 0);
}
static int solution(int n, int max, int current, int index) {
if (n == 0)
return max;
else if (n % 2 == 0 && index == 0)
return 0;
else if (n % 2 == 0 && index > 0)
return solution(n / 2, max, current + 1, index + 1);
else
return solution(n / 2, Math.max(max, current), 0, index + 1);
}
Solution 8:[8]
Objective C Solution
int solution(int N) {
if (N==0)
{
return 0;
}
int maximumGap = -1;
int currentGap = 0;
while(N>0)
{
if (N%2 == 1)
{
if (currentGap>0)
{
maximumGap = maximumGap>currentGap?maximumGap:currentGap;
}else
{
maximumGap = 0;
}
currentGap = 0;
}
else if(maximumGap>-1)
{
currentGap++;
}
N=N/2;
}
return maximumGap;
}
Solution 9:[9]
Java Solution (No recursion - 100% correctness in Codility):
public static int solution(Integer number) {
String binary = Integer.toBinaryString(number);
String[] gaps = binary.split("1");
String biggestGap ="";
for (int i = 0; i < (binary.endsWith("1") ? gaps.length: gaps.length-1); i++) {
if (gaps[i].contains("0") && gaps[i].length()>biggestGap.length())
biggestGap = gaps[i];
}
return biggestGap.length();
}
Solution 10:[10]
I got this solution without using recursion.
def solution(N):
number = str(bin(N))[2:]
current = 0
max_ = 0
started = False
for e in number[::-1]:
if e == '1':
started = True
if current > max_:
max_ = current
current = 0
else:
if started:
current = current + 1
return max_
Solution 11:[11]
The optimal solution that takes in account the boundaries and exceptional scenarios like: Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps. But most code I have seen above will returns 5. Which is wrong. Here is an optimal solution that passes all tests:
public int solution(int N) {
int result = 0;
while (N > 0) {
if ((N & 1) == 1) {
int temp = 0;
while ((N >>= 1) > 0 && ((N & 1) != 1)) {
temp++;
}
result = Math.max(result, temp);
} else {
N >>= 1;
}
}
return result;
}
Solution 12:[12]
My Javascript ES6 Solution with default function parameter
Also handled all possible errors
function solution(N = 0) {
N = +N;
if (N !== N) {
return 0;
}
const binaryList = N.toString(2).split("");
let maxGap = 0;
let currentGap = 0;
binaryList.forEach(item => {
if (item === "0") {
current++;
} else {
if (currentGap > maxGap) {
maxGap = currentGap;
}
currentGap = 0;
}
});
return max;
}
Solution 13:[13]
def solution(N):
max_gap = 0
current_gap = 0
# Skip the tailing zero(s)
while N > 0 and N % 2 == 0:
N //= 2
while N > 0:
remainder = N % 2
if remainder == 0:
# Inside a gap
current_gap += 1
else:
# Gap ends
if current_gap != 0:
max_gap = max(current_gap, max_gap)
current_gap = 0
N //= 2
return max_gap
if __name__ == '__main__':
solution(N)
// Test Cases:
// N = 9 (1001), Expected = 2
// N = 529 = (1000010001), Expected = 4
// N = 51272 (1100100001001000), Expected = 4
// N = 15 (1111), Expected = 0
// N = 53 (110101), Expected = 1
// N = 2147483647 (1111111111111111111111111111111), Expected = 0
// N = 2147483648 (10000000000000000000000000000000), Expected = 0
// N = 0 (0), Expected = 0
// N = -1 (null), Expected = 0
// N = "A" (null), Expected = 0
// N = null (null), Expected = 0
// N = [blank] (null), Expected = 0
Solution 14:[14]
The solution by hemantvsn is great except the trailing zeros which need to be removed
private static int solution(int N) {
int gap = 0;
String binaryStr = Integer.toBinaryString(N);
String[] zeroArrays = binaryStr.split("1");
String[] zeroTruncated = new String[0];
System.out.println(Arrays.toString(zeroArrays));
if (Integer.lowestOneBit(N) != 1) {
zeroTruncated = Arrays.copyOf(zeroArrays, zeroArrays.length-1);
}
for(String zeroArray : zeroTruncated) {
gap = zeroArray.length() > gap ? zeroArray.length() : gap;
}
return gap;
}
Solution 15:[15]
try this. I'm tyring without using recursive.
private static int binaryGap(int N){
int gap1 = 0, gap2 = 0, gapCounter = 0;
for(int i = N; i>=0; i--)
{
if(N < 1) break;
//binary 0
if(N%2 == 0) {
gap1++;
}
//binary 1
else
{
gap2 = gap2 > gap1 ? gap2 : gap1;
gap1 = 0;
gapCounter++;
}
if(gapCounter==1) gap2=0;
N = N/2;
}
return gap2;
}
Solution 16:[16]
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int N) {
int b;
int zeroCounter = 0;
int prev = 0;
int c = -1;
while (N) {
b = N % 2;
N = N / 2;
if ((b==1)||(c==0)) {
c=0;
//printf("%d", b);
if (b == 1) {
//printf("%d", b);
//checkTrailZero=prev;
if (prev < zeroCounter) {
prev = zeroCounter;
}
zeroCounter = 0;
} else {
zeroCounter++;
// printf("--%d--", zeroCounter);
}
}
}
//printf("longest%d", prev);
return prev;}
Solution 17:[17]
Here is working code with all the test cases passed,
package org.nishad;
import java.util.Arrays;
public class BinaryGap {
public static void main(String[] args) {
int N = 1;
int result;
//converting integer to binary string
String NString = Integer.toBinaryString(N);
//Removing the Trailing Zeros
NString = NString.replaceFirst("0*$","");
//Split the binary string by one or more one(regex) for arrays of zeros
String[] NStrings = NString.split("1+");
//Storing the array length
int length = NStrings.length;
if(length==0) // if length is zero no gap found
result = length;
else
{
//Sorting the array to find the biggest zero gap
Arrays.sort(NStrings, (a, b)->Integer.compare(a.length(), b.length()));
result = NStrings[length-1].length();
}
System.out.println(NString);
System.out.println(result);
}
}
Solution 18:[18]
Please just do it:
class Solution {
public int solution(int N) {
int gap = 0;
int current = -1;
while(N>0) {
if(N%2!=0) {
if(current>gap)
gap = current;
current = 0;
} else if(current>=0){
current++;
}
N=N>>1;
}
return gap;
}
}
The definitive!
Thanks!!!!
Solution 19:[19]
Javascript solution during Decimal to binary conversion.
function solution(N) {
let maxGap = 0, currentSegmentGap = 0;
let init = false;
while(N > 0) {
const binDgt = N%2;
if(binDgt) {
currentSegmentGap = 0;
init = true;
} else if(init) {
currentSegmentGap++;
maxGap = maxGap > currentSegmentGap? maxGap: currentSegmentGap;
}
N = Math.floor(N/2);
}
return maxGap;
}
Solution 20:[20]
Java Solution (100% correctness in Codility)
int solution(int N) {
int tempGap=0, gap=0;
String binaryString = Integer.toBinaryString(N);
int i =0;
while(i < binaryString.length()) {
if(binaryString.charAt(i) == '1') {
// initialize tempGap to hold binary gap temporarily and increment the index pointing to binary array
++i;
tempGap = 0;
// move until we encounter '1' or end of array is reached
while(i < binaryString.length() && binaryString.charAt(i) != '1') {
++i;
tempGap++;
}
// in case, end of array is reached but we did not find '1'
if (i >= binaryString.length()) {
tempGap = 0;
}
} else {
++i;
}
if (tempGap>gap) {
gap = tempGap;
}
}
return gap;
}
Solution 21:[21]
My solution is written in Swift 4 with a totally different logic (without recursion), which finds the longest binary gap, also facilitates finding the current binary gap. 100% test cases passed.
Complexity: O(n)
public func solution(_ 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
}
}
Sample test cases with output:
Binary String of "2" is: "10"
Position of 1's: [0]
The longest binary gap is 0
Binary String of "4" is: "100"
Position of 1's: [0]
The longest binary gap is 0
Binary String of "6" is: "110"
Position of 1's: [0, 1]
The longest binary gap is 0
Binary String of "32" is: "100000"
Position of 1's: [0]
The longest binary gap is 0
Binary String of "170" is: "10101010"
Position of 1's: [0, 2, 4, 6]
The longest binary gap is 1
Binary String of "1041" is: "10000010001"
Position of 1's: [0, 6, 10]
The longest binary gap is 5
Binary String of "234231046" is: "1101111101100001010100000110"
Position of 1's: [0, 1, 3, 4, 5, 6, 7, 9, 10, 15, 17, 19, 25, 26]
The longest binary gap is 5
Solution 22:[22]
@saka1029 has provided a nice solution but it does not cover all the test cases. Here is a solution that covers all cases.
public int solution(int N) {
return solution(N, 0, 0, false);
}
static int solution(int n, int max, int count, boolean isOn) {
if (n == 0)
return max;
else if (n % 2 == 0){
count = isOn? count+1 : count;
return solution(n / 2, max, count, isOn);
}
else{
isOn=true;
max = count>max?count:max;
return solution(n / 2, Math.max(max, count), 0, isOn);
}
}
Solution 23:[23]
Here is another Java solution (recursive and iterative versions) with O(log n) time complexity and 100% correctness, i.e. handling the trailing zeros condition, which avoids the use of the integer binary string.
Recursive:
class Solution {
public int solution(int N) {
return binaryGapRecursive(N, 0, null);
}
private int binaryGapRecursive(int n, int maxGap, Integer currentGap) {
int quotient = n / 2;
if (quotient > 0) {
int remainder = n % 2;
if (remainder == 1) {
if (currentGap != null) {
maxGap = Math.max(maxGap, currentGap);
}
currentGap = 0;
} else if (currentGap != null) {
currentGap++;
}
return binaryGapRecursive(quotient, maxGap, currentGap);
} else {
return currentGap != null ? Math.max(maxGap, currentGap) : maxGap;
}
}
}
Iterative:
class Solution {
public int solution(int n) {
int maxGap = 0;
Integer currentGap = null;
while (n > 0) {
int remainder = n % 2;
if (remainder == 1) {
if (currentGap != null) {
maxGap = Math.max(maxGap, currentGap);
}
currentGap = 0;
} else if (currentGap != null) {
currentGap++;
}
n = n / 2;
}
return currentGap != null ? Math.max(maxGap, currentGap) : maxGap;
}
}
Solution 24:[24]
I'm tyring code
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;
public class Solution {
public int solution(int N) {
// write your code in Java SE 8
int result = 0;
// ?? 2??? ??
String binary = Integer.toBinaryString(N);
// ??? 1 ??
int firstOneIdx = 0;
// ?? 1 ??
int nextOneIdx = 0;
// ?? loop? 2?? ??? ??
for (int i = 0; i <= binary.length(); i++) {
// ???? ??? ??
if (i == 0) {
firstOneIdx = binary.indexOf("1");
}
// ??? ??? ?? 1 ??
nextOneIdx = binary.indexOf("1", firstOneIdx + 1);
// ?? 1? ??? loop ??
if (nextOneIdx == -1) {
break;
}
// ?
int temp = nextOneIdx - firstOneIdx - 1;
// ?? ?? ???? ?? ?? ??
if (temp > result) {
result = temp;
}
// ??? ???? ??
firstOneIdx = nextOneIdx;
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
Random random = ThreadLocalRandom.current();
for (int i = 0; i< 10000; i++){
int input = random.nextInt(2147483647);
int result = solution.solution(input);
System.out.println("input = "+input+" result = "+result);
}
}
}
Solution 25:[25]
class Solution { //Java Solution (100% correctness in Codility)
public int solution(int N) {
// write your code in Java SE 8
Integer candidate = new Integer(N);
String binStr = candidate.toBinaryString(N);
char[] binArr = binStr.toCharArray();
// System.out.println("Binary String: " + binStr);
char c, c1;
int counter = 0;
for (int i = 0; i < binStr.length();) {
// c = binStr.charAt(i);
c = binArr[i];
// System.out.println("c: " + c);
i++;
if (c == '1') {
int tempCounter = 0;
for (int j = 0, k = i; j < binStr.length() - 1; j++, k++) {
if (i < binStr.length()) {
c1 = binArr[i];
} else {
break;
}
// System.out.println("c1: " + c1);
if (c1 == '1') {
if (counter < tempCounter)
counter = tempCounter;
break;
} else {
// System.out.println("inside counter...");
tempCounter++;
i++;
}
// i=k;
}
}
}
// System.out.println("Counter: " + counter);
return counter;
}
}
Solution 26:[26]
Kotlin solution:
fun binaryGap(number: Int): Int {
return number.toString(2)
.trimEnd { it == '0' }
.split("1")
.map { it.length }
.max() ?: 0
}
Solution 27:[27]
Here is the perfect solution 100 out of 100 point using Java and recursion. It did pass test of n = 128 with binary value of 10100101 and the ans. 2 and n = 592 with binary value of 1001010000 and the ans. 2.
class Solution {
public int solution(int n) {
return solution(n, 0, 0, 0);
}
static int solution(int n, int max, int current, int ones) {
if (n == 0) {
return max;
} else if (n % 2 == 0) {
return solution(n / 2, max, ++current, ones);
} else {
max = ones == 0 ? ones : Math.max(max, current);
return solution(n / 2, max, 0, ++ones);
}
}
}
Solution 28:[28]
100% Binary Gap solution without recursion
public static int solution(int N) {
String binary = Integer.toString(N, 2);
int length = binary.length();
int trailingZeros = 0;
// Get the length of trailing zeros
for (int i = length - 1; i > 0; i--) {
if (binary.charAt(i) == '0') {
trailingZeros++;
}
else if (binary.charAt(i) == '1') {
break;
}
}
// length of binary string to consider
int lengthToConsider = length - trailingZeros;
System.out.println(lengthToConsider);
int highestGap = 0;
int zeroGapCount = 0;
for (int i = 1; i < lengthToConsider; i++) {
// Count all subsequent zeros
if (binary.charAt(i) == '0') {
zeroGapCount++;
}
// else if 1 found then calculate highestGap as below
else if (binary.charAt(i) == '1') {
if (highestGap <= zeroGapCount) {
highestGap = zeroGapCount;
}
// make the zeroGapCount as zero for next loop
zeroGapCount = 0;
}
}
return highestGap;
}
Solution 29:[29]
Here is my solution without recursion. 100% tests are passed in Codability's application
public class Solution {
int counter = 0;
Set<Integer> binaryGap = new HashSet<>();
String binaryNumber;
public int solution(int N) {
binaryNumber = convert2Binary(N);
IntStream.range(1, binaryNumber.length())
.boxed()
.forEach(calculateBinaryGapConsumer);
return getMaxBinaryGap();
}
private String convert2Binary(int N) {
return Integer.toBinaryString(N);
}
Consumer<Integer> calculateBinaryGapConsumer = i -> {
char currentChar = binaryNumber.charAt(i);
char previousChar = binaryNumber.charAt(i-1);
if (previousChar == '1' && currentChar == '0') {
increaseCounter();
} else if (previousChar == '0' && currentChar == '0') {
increaseCounter();
} else if (previousChar == '0' && currentChar == '1') {
saveBinaryGap();
makeCounterZero();
}
//No need to handle case previousChar == '1' && currentChar == '1'.
};
private void saveBinaryGap() {
binaryGap.add(counter);
}
private void increaseCounter() {
counter++;
}
private void makeCounterZero() {
counter = 0;
}
private int getMaxBinaryGap() {
return binaryGap.stream().mapToInt(v->v).max().orElse(0);
}
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow