Arrays serve as fundamental building blocks in computer science, demanding effective manipulation for diverse algorithms and applications. A common task involves relocating all zeroes to the end of an array, a challenge encountered in various scenarios. In this blog post, we will explore three distinct approaches in C++, complete with examples and outputs.
Approach 1: Naive Method
The initial approach employs a brute force method, traversing the array and relocating non-zero elements to the front. This straightforward method guarantees that all zeroes will accumulate at the array's tail.
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 method can be optimized using a two-pointer technique. It involves maintaining two pointers: one to iterate through the array and another to track the position for inserting 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 alternative approach involves counting the number of zeroes in the array and subsequently filling the array accordingly. This method avoids unnecessary swaps, ensuring a linear time complexity.
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 conclusion, relocating all zeroes to the end of an array can be achieved through diverse approaches . The selection of a method depends on factors such as a rray size, zero frequency , and desired time complexity . Understanding these techniques equips programmers with versatile tools for array manipulation in C++.