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

Question

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;
}

it's i+1, as I'm comparing every element with their adjacent ones. @WeatherVane — UTKARSH LUCIFER, Jun 08 '22 at 07:27
You are writing outside the array bounds with `swap(arr[j+1], arr[j]);` — Weather Vane, Jun 08 '22 at 07:27
It isn't `i+1`, otherwise you will end up swapping `arr[n], arr[n-1]`, which is out of bounds, and will overwrite the next variable after `arr[]`. which is, guess what? `n`. It should be `j < i`. — user207421, Jun 08 '22 at 07:29
You are not comparing every element with the adjacent one, you are comparing with 0. You are *swapping* with the adjacent element, and if `[j]` is the last element then you'll break something. "Why is it so that the value of n becomes 0 after calling the function." — Weather Vane, Jun 08 '22 at 07:29
@UTKARSHLUCIFER *put all the zeroes to the end of the array* -- [See this](https://stackoverflow.com/questions/27003664/good-c-solutions-to-the-bring-all-the-zeros-to-the-back-of-the-array-intervi/27003708#27003708). No loop is required. Basically, this is a 1-line solution using `std::partition`. — PaulMcKenzie, Jun 08 '22 at 07:36
@UTKARSHLUCIFER -- [Solution using std::stable_partition](https://godbolt.org/z/9ncG44jzE). Also, it seems you may have gotten this question from one of those "competitive coding" websites. Well, the one-line solution is more "competitive" than what you are trying to do. The answer is a one-liner (less typing), and it works. — PaulMcKenzie, Jun 08 '22 at 07:42
See [Why should I not #include ?](https://stackoverflow.com/q/31816095) and [Why using namespace std is bad practice](https://stackoverflow.com/questions/1452721). — prapin, Jun 08 '22 at 09:46

chqrlie · Answer 1 · 2022-06-08T08:58:12.540

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(N²) 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; });
}

@UTKARSHLUCIFER Define 'doesn't help'. It should cure `n` becoming zero at least, which is what you actually asked about. — user207421, Jun 08 '22 at 08:09

score 0 · Accepted Answer · answered Jun 08 '22 at 07:37

0

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

answered Jun 08 '22 at 07:37

Avinash

875
6
20

should not `i` start with 1? otherwise if `arr[0]` is non-zero, it gets swapped with itself. You can avoid an extra loop by starting with 1. – Aamir Jun 08 '22 at 08:02
Doesn't answer the question that was asked, which was about why `n` became zero. – user207421 Jun 08 '22 at 08:09
@Aamir No it shouldn't. What you're saying is possible if `arr[0]` is always equals to `0` – Avinash Jun 08 '22 at 08:09

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

2 Answers2