C++ Program to move all zeros to the end of the array
Write a program to move all the zeros in the arr[] to the end. The order of the non-zero elements should not be altered and all the zeros should be placed to the right side of the array.
Example
Input:
arr[] = {1, 2, 0, 4, 3, 0, 6, 0};
Output:
arr[] = {1, 2, 4, 3, 6, 0, 0, 0};
Explanation
All the non-zero elements are aligned to the left-hand side of the array without changing the sequence number
Input:
arr[] = {1, 2, 0, 0, 0, 3, 5};
Output:
arr[] = {1, 2, 3, 5, 0, 0, 0};
Naive approach
- Traverse the arr[] from left to right.
- While traversing, maintain the count of non-zero elements. For every non-zero element, change arr[i] with arr[count].
- Increment the count.
- Now all non-zero elements have been shifted to the front and 'count' is set as the index of the first 0. Make all elements 0 from count to end.
C++ code
#include <iostream>
using namespace std;
// function to move zeros to the right
void pushZerosTotheright(int arr[], int n)
{
int count = 0; // Count of non-zero elements
// 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)
arr[count++] = arr[i]; // here count is
// incremented
// 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;
}
int main()
{
int arr[] = {1, 2, 0, 4, 3, 0, 6, 0};
int n = sizeof(arr) / sizeof(arr[0]); // find size of the array
pushZerosTotheright(arr, n); // call the function
cout << "The output array rearranged is :\n";
for (int i = 0; i < n; i++)
cout << arr[i] << " "; // print the elements
return 0;
}
Output
The output array rearranged is :
1 2 4 3 6 0 0 0
C code
#include <stdio.h>
// function to move zeros to the right
void pushZerosTotheright(int arr[], int n)
{
int count = 0; // Count of non-zero elements
// 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)
arr[count++] = arr[i]; // here count is
// incremented
// 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;
}
int main()
{
int arr[] = {1, 2, 0, 4, 3, 0, 6, 0};
int n = sizeof(arr) / sizeof(arr[0]); // find size of the array
pushZerosTotheright(arr, n); // call the function
printf( "The output array rearranged is :\n");
for (int i = 0; i < n; i++)
printf("%d ",arr[i]); // print the elements
return 0;
}
Output
The output array rearranged is :
1 2 4 3 6 0 0 0
Time complexity - O(n)
Space complexity - O(1)
Approach 2
The optimised approach checks the non-zero element and exchange with the arr[i] positioned element.
Algorithm
moveZerosToEndOfTheArray(arr, n)
Initialize count = 0
for i = 0 to n-1
if (arr[i] != 0) then
swap(arr[count++], arr[i])
C++ code
#include <iostream>
using namespace std;
// function to move zeros to the right
void pushZerosTotheright(int arr[], int n)
{
// Count of non-zero elements
int count = 0;
// Traverse the array. If arr[i] is non-zero, then
// swap the element at index 'count' with the
// element at index 'i'
for (int i = 0; i < n; i++)
if (arr[i] != 0)
swap(arr[count++], arr[i]);
}
int main()
{
int arr[] = {1, 2, 0, 4, 3, 0, 6, 0};
int n = sizeof(arr) / sizeof(arr[0]); // find size of the array
pushZerosTotheright(arr, n); // call the function
cout << "The output array rearranged is :\n";
for (int i = 0; i < n; i++)
cout << arr[i] << " "; // print the elements
return 0;
}
Output
The output array rearranged is :
1 2 4 3 6 0 0 0
Time complexity - O(n)
Space complexity - O(1)