Approach with efficient zero shiftings

Software Development
#1

Approach with efficient zero shiftings:

For a given array of n integers and assume that ‘0’ is an invalid number and all others as a valid number. Convert the array in such a way that if both current and next element is valid then double current value and replace the next number with 0. After the modification, rearrange the array such that all 0’s shifted to the end.

Although the above solution is efficient, we can further optimise it in shifting zero algorithms by reducing the number of operations.

In the above shifting algorithms, we scan some elements twice when we set the count index to last index element to zero.

Efficient Zero Shifting Algorithms:

int lastSeenPositiveIndex = 0; for( index = 0; index < n; index++) { if(array[index] != 0) { swap(array[index], array[lastSeenPositiveIndex]); lastSeenPositiveIndex++; } }

  • C++
  • Java
  • Python3
  • Javascript

class GFG {

// Function For Swaping Two Element Of An Array

public static void swap( int [] A, int i, int j)

{

int temp = A[i];

A[i] = A[j];

A[j] = temp;

}

// shift all zero to left side of an array

static void shiftAllZeroToLeft( int array[], int n)

{

// Maintain last index with positive value

int lastSeenNonZero = 0 ;

for ( int index = 0 ; index < n; index++) {

// If Element is non-zero

if (array[index] != 0 ) {

// swap current index, with lastSeen

// non-zero

swap(array, array[index],

array[lastSeenNonZero]);

// next element will be last seen non-zero

lastSeenNonZero++;

}

}

}

}