4

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));
    }

}
Improve this question
0

37 Answers 37

Reset to default
1
2
0

using javascript without recursion

function solution(N) {
  var binary = N.toString(2);
  var lengths = [];
  var length = -1;

  for (var i = 0; i < binary.length; i++) {
      if (
           (binary[i] === 1 && binary[i+1] === 0 && length === -1) 
           || (binary[i] === 0 && length >= 0)
         ) {
            length++;
      }
      else if (binary[i] === 1 && length >= 0) {
          lengths.push(length);
          length = -1;
          i--;
      }
  }

  return lengths.length ? Math.max(...lengths) : 0;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

One more way

static int solution(int n) {
    String binaryNUmber = Integer.toBinaryString(n);
    char[] arr = binaryNUmber.toCharArray();

    int startIndex = -1;
    boolean found = false;
    int gap = 0;
    int newGap = 0;
    for(int i=0; i< arr.length; i++) {
        if(arr[i] == '1' && startIndex == -1) {
            startIndex = i+1;
            found = true;
            i += 1;
        }
        if(i<arr.length && found) {
            if(arr[i] == '0') {
                gap +=1;
            } else
             if(arr[i] == '1') {
                startIndex = i+1;
                if(newGap < gap) {
                    newGap  = gap;
                } 
                gap = 0;
            }
        }
    }
    return newGap;
}
Improve this answer

Comments

0

Kotlin Solution

fun solution(N: Int): Int {
    var maxGap = 0
    var gap = 0
    for (char in N.toString(2))
        if (char == '1') {
            if (gap > maxGap) maxGap = gap
            gap = 0
        } else if (gap != -1) gap++

    return maxGap
}
Improve this answer

Comments

0

This is also an extremely simple solution. This problem can also be solved by keeping track of the index where the 1 occurred(in binary). The solution does not use any array and any complex method. It is simple if else logic.

    public int solution(int N) {
    int saveN = 0;
    int digit =0;
    int value =0;
    int savedi =0;
    int resultVal =0;
    saveN = N;
    bool firstHit = true;

    //First calculate the total digits
    while(N != 0)
    {
        digit++;
        N = N / 2;
    }

    N = saveN;

    for(int i =0; i<digit;i++)
    {
        // If 1 is found at the ith place
        if((N & (0x01 << i)) == (0x01 << i))
        {
            if(firstHit)
            {
                savedi = i;// save i value
                firstHit = false;
            }
            else
            {
                value = i - savedi;
                if(resultVal < value)
                    resultVal = value;
                firstHit = true;
                // 1 found again so go 1 iteration back and save the 1's position 
                i--;
            }
        }
    }

    // sub 1 as it gives 1 more than true result  
    resultVal = resultVal - 1;

    //handle if a single 1 is found
    if(resultVal < 0)
        return 0;
    else
        return resultVal;        
}
Improve this answer

Comments

0

My 100% JavaScript solution without using recursion:

function solution(N) {

    const binary = N.toString(2);
    let gap = 0;
    let maxGap = 0;

    for (let i = 1, len = binary.length; i < len; i++) {

        const prev = binary[i - 1];
        const cur = binary[i];

        if (prev === '1' && cur === '0') {
            gap = 1; // start counting the gap
        }
        
        if (prev === '0' && cur === '0' && gap > 0) {
            gap++; // increment the gap if the counting was previously started
        }
        
        if (prev === '0' && cur === '1' && gap > maxGap) {
            maxGap = gap; // save the gap if it is the largest
        }


    }

    return maxGap;

}
Improve this answer

Comments

0

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.

Time 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
Improve this answer

Comments

-1 
int solution(N) {

   int num = N,
    currentLongest=0,
    lastLongest=0,
    start=0;

  while(num>0){
    int rem = num%2;
        num = num/2;

    if(rem == 1){
        if(lastLongest < currentLongest){
            lastLongest = currentLongest;
        }
        currentLongest = 0;
        start = true;
    }else{
        if(start)
         ++currentLongest;
       }
   }
  return lastLongest;
}
Improve this answer

1 Comment

no explanation of the code or description was given
1
2

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.