Double the first element and move zero to end

Hello Everyone,

For a given array of n integers and assume that ‘0’ as an invalid number and all other 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.
Examples:

Input : arr[] = {2, 2, 0, 4, 0, 8}
Output : 4 4 8 0 0 0

Input : arr[] = {0, 2, 2, 2, 0, 6, 6, 0, 0, 8}
Output : 4 2 12 8 0 0 0 0 0 0

Approach: First modify the array as mentioned, i.e., if the next valid number is the same as the current number, double its value and replace the next number with 0.
Algorithm for Modification:

  1. if n == 1 2. return 3. for i = 0 to n-2 4. if (arr[i] != 0) && (arr[i] == arr[i+1]) 5. arr[i] = 2 * arr[i] 6. arr[i+1] = 0 7. i++

After modifying the array, Move all zeroes to end of array

// C++ implementation to rearrange the array

// elements after modification

#include <bits/stdc++.h>

using namespace std;

// function which pushes all zeros to end of

// an array.

void pushZerosToEnd( int arr[], int n)

{

// Count of non-zero elements

int count = 0;

// Traverse the array. If element encountered

// is non-zero, then replace the element at

// index 'count' with this element

for ( int i = 0; i < n; i++)

if (arr[i] != 0)

// here count is incremented

arr[count++] = arr[i];

// Now all non-zero elements have been shifted

// to front and 'count' is set as index of

// first 0. Make all elements 0 from count

// to end.

while (count < n)

arr[count++] = 0;

}

// function to rearrange the array elements

// after modification

void modifyAndRearrangeArr( int arr[], int n)

{

// if 'arr[]' contains a single element

// only

if (n == 1)

return ;

// traverse the array

for ( int i = 0; i < n - 1; i++) {

// if true, perform the required modification

if ((arr[i] != 0) && (arr[i] == arr[i + 1])) {

// double current index value

arr[i] = 2 * arr[i];

// put 0 in the next index

arr[i + 1] = 0;

// increment by 1 so as to move two

// indexes ahead during loop iteration

i++;

}

}

// push all the zeros at the end of 'arr[]'

pushZerosToEnd(arr, n);

}

// function to print the array elements

void printArray( int arr[], int n)

{

for ( int i = 0; i < n; i++)

cout << arr[i] << " " ;

}

// Driver program to test above

int main()

{

int arr[] = { 0, 2, 2, 2, 0, 6, 6, 0, 0, 8 };

int n = sizeof (arr) / sizeof (arr[0]);

cout << "Original array: " ;

printArray(arr, n);

modifyAndRearrangeArr(arr, n);

cout << "\nModified array: " ;

printArray(arr, n);

return 0;

}

Output:

Original array: 0 2 2 2 0 6 6 0 0 8 Modified array: 4 2 12 8 0 0 0 0 0 0

Time Complexity: O(n).

Approach with efficient zero shiftings:

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

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

// Utility Function For Swaping Two Element Of An Array

void swap( int & a, int & b) { a = b + a - (b = a); }

// shift all zero to left side of an array

void shiftAllZeroToLeft( int array[], int n)

{

// Maintain last index with positive value

int lastSeenNonZero = 0;

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

{

// If Element is non-zero

if (array[index] != 0)

{

// swap current index, with lastSeen non-zero

swap(array[index], array[lastSeenNonZero]);

// next element will be last seen non-zero

lastSeenNonZero++;

}

}

}