Friday 24 July 2015

Shift zeros to left and non-zeros to right

Given arrays of 0s and nonzeros. Shift zeros to left and non-zeros to right.

For example,
 0 9 2 6 0 1 7 8 0 0 9

Take a variable and assign it first non-zero position.

Position = 1 here, since elements in array starts from 0.

Next start other counter from position + 1, goto till end, if you find any zero element, swap it with position, increment position by 1 repete this logic until, you reach end of the array.

Algorithm like below.

Step 1: in arr[], i, position.

Step 2: find first non-zero position.
for(i = 0; i<arr.length; i++){
         if(a[i] != 0){
                  position = i;
break;
}
}

Step 3: for(i = position + 1; i < arr.length; i++){
         if(a[i] != 0){
                  continue;
         }
         swap(a[i], a[position]);
         position++;
}

For the above example, following is the sequence for every swapping.

Step 1: 0 9 2 6 0 1 7 8 0 0 9 (Initial position = 1, i = 2)

Step 2: 0 0 2 6 9 1 7 8 0 0 9 (After swapping position = 2, i = 5)

Step 3: 0 0 0 6 9 1 7 8 2 0 9 (After swapping position=3,  i=8)

Step 4: 0 0 0 0 9 1 7 8 2 6 9


Following is the complete application.
import java.util.Objects;

public class MoveZeros {

 public static void moveZeros(int arr[]) {
  Objects.requireNonNull(arr);

  if (arr.length < 2)
   return;

  int position = -1;
  for (int j = 0; j < arr.length; j++)
   if (arr[j] != 0) {
    position = j;
    break;
   }

  for (int j = position + 1; j < arr.length; j++) {
   if (arr[j] != 0)
    continue;

   int temp = arr[j];
   arr[j] = arr[position];
   arr[position] = temp;

   position++;
  }
 }

}


Following are the junit test cases.

import static org.junit.Assert.assertTrue;

import java.util.Arrays;

import org.junit.Test;

public class MoveZerosTest {

 @Test
 public void test1() {
  int arr[] = { 0, 9, 2, 6, 0, 1, 7, 8, 0, 0, 9 };
  int expected[] = { 0, 0, 0, 0, 9, 1, 7, 8, 2, 6, 9 };

  MoveZeros.moveZeros(arr);
  assertTrue(Arrays.equals(arr, expected));

  int[] arr1 = { 0, 0, 0, 0, 0, 0, 5, 6, 7, 0 };
  int[] expected1 = { 0, 0, 0, 0, 0, 0, 0, 6, 7, 5 };

  MoveZeros.moveZeros(arr1);
  assertTrue(Arrays.equals(arr1, expected1));

  int[] arr2 = { 5, 6, 7, 8, 0, 0, 0 };
  int[] expected2 = { 0, 0, 0, 8, 5, 6, 7 };
  MoveZeros.moveZeros(arr2);
  assertTrue(Arrays.equals(arr2, expected2));

  int[] arr3 = { 0, 5 };
  int[] expected3 = { 0, 5 };
  MoveZeros.moveZeros(arr3);
  assertTrue(Arrays.equals(arr3, expected3));

  int[] arr4 = { 5, 0 };
  int[] expected4 = { 0, 5 };
  MoveZeros.moveZeros(arr4);
  assertTrue(Arrays.equals(arr4, expected4));
 }

 @Test
 public void test2() {
  int arr[] = {};
  int expected[] = {};

  MoveZeros.moveZeros(arr);

  assertTrue(Arrays.equals(arr, expected));
 }

 @Test(expected = NullPointerException.class)
 public void test3() {
  MoveZeros.moveZeros(null);
 }

}



No comments:

Post a Comment