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)