reverse an array without changing position of zero-CodePudding

I have just tried some of the data structures questions along with my friends. I encountered this problem from one of my friends who is also not able to solve it.

Question: Reverse an array without changing position of zeroes. example : if array has has 0 5 7 8 0 9 then the result should be 0 9 8 7 0 5.

I tried it but it does not do it correctly in all cases, I am sorry if code looks ugly I am a novice right now.

#include<iostream>
using namespace std;
int main()
{
    int arr[100], tot, i, j, temp;
    cout<<"Enter the Size for Array: ";
    cin>>tot;
    cout<<"Enter "<<tot<<" Array Elements: ";
    for(i=0; i<tot; i  )
        cin>>arr[i];
    cout<<"\nThe Original Array is:\n";
    for(i=0; i<tot; i  )
        cout<<arr[i]<<" ";
    j = tot-1;
    for(i=0; i<j; i  , j--)
    {
        if(arr[i] == 0) {
            i  ;
            continue;
        }else if(arr[j] == 0) {
           j--;
           continue;
        }
        else {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    cout<<"\n\nThe Reverse of Given Array is:\n";
    for(i=0; i<tot; i  )
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}

I have tried the above code but it does not give the correct results.

CodePudding user response：

The issue here is the fact that you're modifying the loop variables i and j in every iteration of the loop; you need to update it only in the case of elements being swapped:

for(i=0; i<j;)
{
    if(arr[i] == 0) {
        i  ;
    }else if(arr[j] == 0) {
       j--;
    }
    else {
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
          i;
        --j;
    }
}

Demo on godbolt.org

CodePudding user response：

Seems you need the next logic inside the loop:

i = 0;
j = tot-1;
while(i<j)   {
        while (arr[i]==0 && i<j)
            i  ;
        while (arr[j]==0 && j>i) 
           j--;
        if (i < j) {
          temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
        }
       i  ;
       j--; 
    }

CodePudding user response：

You can use two pointers to switch, simply skipping any 0's.

#include<iostream>
using namespace std;
int main()
{
    int arr[100], tot, i, j, temp;
    cout<<"Enter the Size for Array: ";
    cin>>tot;
    cout<<"Enter "<<tot<<" Array Elements: ";
    for(i=0; i<tot; i  )
        cin>>arr[i];
    cout<<"\nThe Original Array is:\n";
    for(i=0; i<tot; i  )
        cout<<arr[i]<<" ";
    i = 0, j = tot-1;
    while (i < j) {
        if (arr[i]!=0 && arr[j]!=0) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i  ;
            j--;
        } else if (arr[i] == 0) {
            i  ;
        } else {
            j--;
        }
    }
   
    cout << "\n Reverse all elements of the array: " << endl;  
    // use for loop to print the reverse array  
    for ( i = 0; i < tot; i  )  
    {  
        cout << arr[i] << " ";  
    }  
    cout<<endl;
    return 0;
}

You can see this in action here: https://godbolt.org/z/84q3McccW

CodePudding user response：

In your code in the loop:

    if(arr[i] == 0) {
        i  ;
        continue;
    }else if(arr[j] == 0) {
       j--;
       continue;

You increment i when arr[i] is a 0. But then you continue and for the next iteration i is incremented again as part of i , j--. This makes your code skip elements. I suggest to use std::vector and iterators:

#include <iostream>
#include <vector>


int main()
{
    std::vector<int> x{1,2,0,3,4,0,0,0};
    auto begin = x.begin();
    auto end = std::prev(x.end());

    while (begin != end) {
        while(begin != end && *begin == 0)   begin;
        while(begin != end && *end == 0) --end;    
        if (begin != end) {
            std::swap(*begin,*end);
              begin;
            if (begin != end) --end;
        }
    }
    for (const auto& e : x) std::cout << e << " ";
}

output:

4 3 0 2 1 0 0 0

The code starts with iterators to first and last element. In the loop they are advanced while they refer to a 0 and the two didn't cross each other yet. Then the elements are swapped.

If additional memory is acceptable, a much simpler solution is to copy all non zero elements to a second std::vector, std::reverse that vector, then copy back. Alternatively use the ranges library with a filter.

CodePudding user response：

If there were no zeroes to be skipped, the code could be

for (i= 0, j= n-1; i < j; i  , j--)
{
  Swap(a[i], a[j]);
}

Now it "suffices" to skip the zeroes. This gives the modified code

for (i= 0, j= n-1; i < j; i  , j--)
{
  while (i < j && a[i] == 0) i  ;
  while (i < j && a[j] == 0) j--;
  Swap(a[i], a[j]);
}

Notice that the Swap can be performed with i==j, which is useless but harmless, as 0 ≤ i ≤ j < n.

Update: as done by @fabian, you can compress the three loops in one.

for (i= 0, j= n-1; i < j; )
{
  if (a[i] == 0) 
    i  ;
  else if (a[j] == 0) 
    j--;
  else
  { 
    Swap(a[i], a[j]);
    i  ; j--;
  }
}

CodePudding user response：

you need to change the logic of reverse.

#include<iostream>
using namespace std;
int main()
{
    int arr[100], tot, i, j, temp;
    cout<<"Enter the Size for Array: ";
    cin>>tot;
    cout<<"Enter "<<tot<<" Array Elements: ";
    for(i=0; i<tot; i  )
        cin>>arr[i];
    cout<<"\nThe Original Array is:\n";
    for(i=0; i<tot; i  )
        cout<<arr[i]<<" ";
    j = tot-1;
   for ( i = 0, j = tot - 1; i < tot/2; i  , j--)  
    {     
        temp = arr[i];  
        arr[i] = arr[j];  
        arr[j] = temp;  
    }  
    cout << "\n Reverse all elements of the array: " << endl;  
    // use for loop to print the reverse array  
    for ( i = 0; i < tot; i  )  
    {  
        cout << arr[i] << " ";  
    }  
    cout<<endl;
    return 0;
}

I hope this will help