Advertisement
gelita

Bit flip

Feb 14th, 2020
209
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 1.35 KB | None | 0 0
  1. /*
  2. *  Problem 2: Bit Flip
  3. *
  4. *     Given an array of binary values (0 and 1) and N number of flips (convert
  5. *     a 0 to a 1), determine the maximum number of consecutive 1's that can be
  6. *     made.
  7. *
  8. *  Input: An Array of 1's and 0's, and an Integer N denoting the number of
  9. *         flips
  10. *  Output: Integer
  11. *
  12. *  Example: bitFlip([0,1,1,1,0,1,0,1,0,0], 2)
  13. *  Result: 7
  14. */
  15.  
  16.    // Time Complexity:
  17.    // Auxiliary Space Complexity:
  18.  
  19.  import java.io.*;
  20.  import java.util.*;
  21.  
  22.  class Problems {
  23.    
  24.    public static void main(String[] args){
  25.      int[] arr = {0,1,1,1,0,1,0,1,0,0};
  26.      int n = 5;
  27.      System.out.println(BitFlip(arr, n));
  28.    }
  29.    
  30.     public static int BitFlip(int[] arr, int N) {
  31.      int numZeros = 0;
  32.      int len = arr.length;
  33.      for(int i = 0; i< len; i++){
  34.           if(arr[i] == 0){
  35.             numZeros++;
  36.           }
  37.      }
  38.      if(N == numZeros){
  39.        return len;
  40.      }
  41.      //if the array has only 1 zero and there are no flips--> return 0
  42.      if(len == 1 && N == 0){
  43.        return 0;
  44.      }
  45.      int numFlips = N;
  46.      int index = 0;
  47.      while(numFlips > -1 ){
  48.        //if the element is 0 -> flip it and decrement numFlips
  49.        if(arr[index] == 0){
  50.           numFlips--;
  51.           index++;
  52.        }else if(arr[index] == 1){
  53.          index++;
  54.        }
  55.      }
  56.      return index;    
  57.     }
  58.  }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement