Arrays play a crucial role in the field of computer science, requiring efficient handling for a wide range of algorithms and uses. One typical operation involves moving all zero values to the end of an array, a problem that arises in many different situations. This article will delve into three different methods in C++ for accomplishing this task, accompanied by illustrative examples and results.
Approach 1: Naive Method
The first strategy utilizes a brute force technique, iterating through the array and shifting non-zero elements to the beginning. This direct approach ensures that all zero values will gather at the end of the array.
Example:
#include <iostream>
using namespace std;
void moveZeroesToEnd(int arr[], int n) {
int nonZeroCount = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
if (arr[i] != 0) {
arr[nonZeroCount] = arr[i];
nonZeroCount++;
}
}
// Fill remaining positions with zeroes
while (nonZeroCount < n) {
arr[nonZeroCount] = 0;
nonZeroCount++;
}
}
int main() {
int arr[] = {1, 0, 2, 0, 3, 4, 0, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original Array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
moveZeroesToEnd(arr, n);
cout << "\nArray after moving zeroes to the end: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Output:
Original Array: 1 0 2 0 3 4 0 5
Array after moving zeroes to the end: 1 2 3 4 5 0 0 0
Approach 2: Two-Pointer Optimization
The brute force approach can be enhanced by implementing a two-pointer strategy. This technique entails managing two pointers simultaneously: one for traversing the array and the other for keeping track of the location to insert non-zero elements.
Example:
#include <iostream>
using namespace std;
void moveZeroesToEnd(int arr[], int n) {
int nonZeroCount = 0;
// Traverse the array with two pointers
for (int i = 0; i < n; i++) {
if (arr[i] != 0) {
swap(arr[i], arr[nonZeroCount]);
nonZeroCount++;
}
}
}
int main() {
int arr[] = {1, 0, 2, 0, 3, 4, 0, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original Array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
moveZeroesToEnd(arr, n);
cout << "\nArray after moving zeroes to the end: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Output:
Original Array: 1 0 2 0 3 4 0 5
Array after moving zeroes to the end: 1 2 3 4 5 0 0 0
Approach 3: Counting and Filling
An alternate strategy includes tallying the quantity of zeros within the array and then populating the array based on this count. This technique eliminates superfluous exchanges, guaranteeing a time complexity of O(n).
Example:
#include <iostream>
using namespace std;
void moveZeroesToEnd(int arr[], int n) {
int zeroCount = 0;
// Count the number of zeroes
for (int i = 0; i < n; i++) {
if (arr[i] == 0) {
zeroCount++;
}
}
// Fill the array with non-zero elements
int nonZeroIndex = 0;
for (int i = 0; i < n; i++) {
if (arr[i] != 0) {
arr[nonZeroIndex++] = arr[i];
}
}
// Fill the remaining positions with zeroes
while (zeroCount > 0) {
arr[nonZeroIndex++] = 0;
zeroCount--;
}
}
int main() {
int arr[] = {1, 0, 2, 0, 3, 4, 0, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original Array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
moveZeroesToEnd(arr, n);
cout << "\nArray after moving zeroes to the end: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Output:
Original Array: 1 0 2 0 3 4 0 5
Array after moving zeroes to the end: 1 2 3 4 5 0 0 0
Conclusion:
In summary, moving all zeros to the end of a array can be accomplished using various methods. The choice of technique relies on factors like the size of the array, frequency of zeros, and the preferred time complexity. Familiarizing oneself with these strategies provides developers with flexible resources for manipulating arrays in C++.
