-1

I need to find the minimum number of swaps required such that all the 0s and all the 1s are together.

Here is my code:

class GFG {

    static int minSwaps(int arr[], int n) {
        int noOfOnes = 0;
        for (int i = 1; i <= n; i++) {
            if (arr[i] == 1)
            noOfOnes++;
        }
        int x = noOfOnes;
        int maxOnes = Integer.MIN_VALUE;
        int preCompute[] = new int[n];
        if (arr[0] == 1)
            preCompute[0] = 1;
        for (int i = 2; i < n; i++) {
            if (arr[i] == 1) {
                preCompute[i] = preCompute[i - 1] + 1;
            } else {
                preCompute[i] = preCompute[i - 1];
            }
        } 

        for (int i = x - 1; i < n; i++) {
            if (i == (x - 1)) {
                noOfOnes = preCompute[i];
            } else {
                noOfOnes = preCompute[i] - preCompute[i - x];
            }
            if (maxOnes < noOfOnes)
                maxOnes = noOfOnes;
        }

        int noOfZeroes = x - maxOnes;
        return noOfZeroes;
    }

    public static void main (String[] args) { 
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
        for (int test = 1; test <= t; test++) {
            int n = s.nextInt();
            int[] a = new int[n];
            for (int j = 1; j <= n; j++) {
                a[j] = s.nextInt();
            }
            System.out.println(minSwaps(a, n));
            System.out.println("\n");
        }
    }
}

I'm getting the ArrayIndexOutOfBoundsException:

error : Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 4
    at GFG.main(solution.java:56)
Vladimir Vagaytsev
  • 2,871
  • 9
  • 33
  • 36
chitaranjan pradhan
  • 9
  • 4
  • what is your question? – Scary Wombat Jul 30 '19 at 06:15
  • 3
    This loop in your `main` method has wrong bounds: `for (int j = 1; j <= n; j++)`. It will cause the `Exception` due to `int a = new int[n];` declared before. Find out correct bounds (hint: length is not equal to index). I could directly tell you the correct ones, but that would mean stealing your learning effect! – deHaar Jul 30 '19 at 06:15
  • error : Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 4 at GFG.main(solution.java:56) why im getting this error – chitaranjan pradhan Jul 30 '19 at 06:15
  • 1
    @chitaranjanpradhan https://stackoverflow.com/questions/5554734/what-causes-a-java-lang-arrayindexoutofboundsexception-and-how-do-i-prevent-it – Mihir Kekkar Jul 30 '19 at 06:19
  • 1
    Possible duplicate of [What causes a java.lang.ArrayIndexOutOfBoundsException and how do I prevent it?](https://stackoverflow.com/questions/5554734/what-causes-a-java-lang-arrayindexoutofboundsexception-and-how-do-i-prevent-it) – Jeroen Steenbeeke Jul 30 '19 at 06:20
  • Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at GFG.minSwaps(solution.java:41) at GFG.main(solution.java:68) – chitaranjan pradhan Jul 30 '19 at 06:34

1 Answers1

0

It looks like you're trying to do bubblesort. So I copied this bubblesort pseudocode implementation off of Wikipedia and augmented it with a counter:

bubbleSort(Array A)
  swap_counter = 0          // start at 0
  for (n=A.size; n>1; --n){
    for (i=0; i<n-1; ++i){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
        swap_counter++      // count a swap
      }
    }
  }
  return swap_counter       // return the result
Jens Jensen
  • 1,038
  • 1
  • 10
  • 20