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:
- 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++;
}
}
}