n is 0 after passing it as an argument to the function, What seems to be the problem here?

user_13916419 0
Viewed 75

Here the question is to put all the zeroes to the end of the array. I've written the code below, but after passing (arr, n) to the pushzero() function, when I try to print the array, it does nothing, and the value of n changes to zero after calling the pushzero() function.

#include <bits/stdc++.h>

using namespace std;

void pushzero(int arr[], int n) {   
    for (int i = 0; i < n; i++) {   
        for (int j = 0; j < i + 1; j++) {
            if (arr[j] == 0) {
                swap(arr[j+1], arr[j]);
            }
        }
    }
}

int main() {
    int arr[] = { 2, 6, 0, 0, 1, 9, 0, 8, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " " << "\n";
    }
    pushzero(arr, n);
    
    for (int j = 0; j < n; j++) { // n is 0 here
        cout << arr[j] << " ";
    }
    return 0;
}
sorting c++
2 Answers

The code has undefined behavior because the inner loop in pushzero iterates too far:

  • in the last iteration of the outer loop of pushzero, i has the value n - 1
  • the last iteration of the inner loop, j has the value i, hence n - 1,
  • if the test arr[j] == 0 is true, which will happen since there are multiple zeroes in the array, swap will be called to exchange the values of arr[j] and arr[j+1], hence reading and modifying arr[n] which is beyond the end of the array.

This undefined behavior may have surprising consequences, such as the behavior you observe, possibly because n is stored in stack memory just after the array arr, an indication that you disabled optimisations.

Changing the loop test to j < i fixes the out of bounds access but does not achieve your goal. You should write j < n - i - 1 for proper operation.

Here is a modified version:

#include <bits/stdc++.h>

using namespace std;

void pushzero(int arr[], int n) {   
    for (int i = 0; i < n; i++) {   
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] == 0) {
                swap(arr[j+1], arr[j]);
            }
        }
    }
}

int main() {
    int arr[] = { 2, 6, 0, 0, 1, 9, 0, 8, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";

    pushzero(arr, n);
    
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    return 0;
}

The above implementation is suboptimal as it has O(N2) complexity. Below is a simpler one with linear execution time:

void pushzero(int arr[], int n) {   
    int i, j;
    for (i = j = 0; i < n; i++) {   
        if (arr[i] != 0) {
            arr[j++] = arr[i];
        }
    }
    while (j < n) {   
        arr[j++] = 0;
    }
}

Or using the swap() function with slightly more work:

void pushzero(int arr[], int n) {  
    for (int i = 0, j = 0; i < n; i++) {   
        if (arr[i] != 0) {
            swap(arr[i], arr[j++]);
        }
    }
}

You can also use a more idiomatic C++ solution, as suggested by @PaulMcKenzie:

#include <algorithm>

void pushzero(int arr[], int len) {   
    std::stable_partition(arr, arr + len, [](int n) { return n != 0; });
}
user_45932670

You could do it by using 0 as a pivot element and whenever you see a non zero element you will swap it with the pivot element. So all the non zero element will come at the beginning.

void pushzero(int arr[], int n) {  
    int j =0; 
    for (int i = 0; i < n; i++) {   
        if(arr[i] != 0) {
            swap(arr[i], arr[j]);
            j++;
        }
    }
}

Demo: https://godbolt.org/z/oMdxfdWjG

user_146307000
Related