title: Solving Binary Gap using Recursion
body: <p>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.</p>
  
  <p>Example: </p>
  
  <pre><code>input= 9, Binary form = 1001, Answer = 2
  
  input=37, Binary form = 100101, Answer = 2
  </code></pre>
  
  <p>It finds the maximum number of zeros that occur between two 1's in the binary representation. </p>
  
  <p>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?</p>
  
  <pre><code>class BinaryGap {
  
      public int solution(int N){
  
       return solution(N, false, 0);   
      }
      public int solution(int N, boolean prevFlag, int memo) {
  
          if(N&lt;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 &gt; 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));
      }
  
  }
  </code></pre>