CODEWITHSUNDEEP
c++
kagamine
kagamine

Reputation: 11

move zeros in an array to the end

"The question comes under a broad category of "Array Transformation". This category is the meat of tech interviews. Mostly because arrays are such a simple and easy to use data structure. Traversal or representation doesn't require any boilerplate code and most of your code will look like the Pseudocode itself.

The 2 requirements of the question are:

Move all the 0's to the end of array.

All the non-zero elements must retain their original order."

My thinking: to find the zeros and exchange their positions with the last numbers

       /* int swap;
       int n=nums.size()-1;
       for(int i=0;i<nums.size();i--){
           if(nums[i]==0){
               swap = nums[i];
               nums[i] = nums[n];
               nums[n] = swap;
               n--;
           }

       }

My input [0,1,0,3,12] Output [1,3,12,0,0] Diff Expected [1,3,12,0,0]

And I did not know why the correct answer(the part) is :

 (int n = 0, cur = 0; cur < nums.size(); cur++) {
        if (nums[cur] != 0) {
            swap(nums[n++], nums[cur]);
         }
       }
    }

Upvotes: 0

Views: 225

Answers (2)

boB
boB

Reputation: 173

My take on the problem, minimal std library usage. Probably not the most efficient, but it does the trick.

#include "stdafx.h"
#include <iostream>

int main()
{
    int src[]  = { 0, 1, 0, 3, 0, 12 };           // Output: 1 3 12  0 0 0   check
            // = { 0, 3, 0, 1, 0, 0, 12, 0, 5 };  // Output: 3 1 12 5 0 0 0 0 0   check 

    int n = sizeof(src) / sizeof(src[0]);

    for (int x = 0; x < n; x++) {
        for (int y = x + 1; y < n; y++) {
            if (src[x] == 0 && src[y] != 0) {
                int swap = src[x];
                src[x] = src[y];
                src[y] = swap;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        std::cout << src[i] << " ";
    }
    return 0;
}

Upvotes: 0

Shawn
Shawn

Reputation: 52344

Can you use the standard library? std::stable_partition() makes it trivial. Something like

std::stable_partition(nums.begin(), nums.end(),
    [](const auto &n){ return n != 0; });

For the question of how the solution in your post works:

At the start of the first iteration, n is 0, cur is 0, and nums is [0,1,0,3,12]. nums[cur] is 0, so nothing happens. At the start of the second iteration, cur is 1, and nums[cur] is 1, so the swap and increment of n happens.

Now n is 1, cur is 2, and nums is [1,0,0,3,12]. nums[cur] is 0, so nothing happens in the third iteration. In the fourth iteration, with cur now 3, a swap happens. So at the start of the the fifth iteration, n is 2, cur is 4, and nums is [1,3,0,0,12]. I'll leave it to you to work out what happens in that step.

Basically, when n is not equal to cur, it's the index of a 0 element that can be swapped with a non-0 element that cur is the index of. This swapping eventually moves all 0's to the end.

Upvotes: 4

Related Questions