# 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); // 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); // 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); // 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)