Good C++ Solutions to the "Bring All the Zeros to the Back of the Array" Interview Challenge

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

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

C++ optimal way of bring the ones to the front of an array of zeros and ones

There are many solutions to this problem. I shall start with very simple one.

Solution1:
count the number of ones in array and fill the front elements of array with those many ones and rest of the array with zeroes. Following code does that-

void zero_to_front(char* c, int n)
{ 
    int count = 0;
    for(int i=0; i<n; i++)
        if(c[i] == 1) count++;

    for(int i=0; i<n; i++)
        if(i<count) c[i]=1;
        else c[i] = 0

}

Time complexity is: O(n)

Solution2: Each time you find 0 in array look for 1 in following positions in array and swap it. Following code does that.

void zero_to_front(int*c, int n){
    int one_pos = -1;
    for (int i = 0; i < n; i++) {
        if (c[i] == 0) {

            if(one_pos == -1)
                one_pos = i+1;
            //Find the position of first one
            while (one_pos < n && c[one_pos] != 1 )
                one_pos++;
            //swap(c[i], c[one_pos]);
            int temp = c[i];
            c[i] = c[one_pos];
            c[one_pos] = temp;
        }

    }
}

Time complexity is: O(n)

Solution3:
Sort the array in reverse order.
Time complexity is: O(nlogn)

Algorithm to generate all possible arrays of ones and zeros of a given length

How would you count manually on paper? You would check the last digit. If it is 0, you set it to 1. If it is already 1, you set it back to 0 and continue with the next digit. So it's a recursive process.

The following program generates all possible combinations by mutating a sequence:

#include <iostream>

template <typename Iter>
bool next(Iter begin, Iter end)
{
    if (begin == end)      // changed all digits
    {                      // so we are back to zero
        return false;      // that was the last number
    }
    --end;
    if ((*end & 1) == 0)   // even number is treated as zero
    {
        ++*end;            // increase to one
        return true;       // still more numbers to come
    }
    else                   // odd number is treated as one
    {
        --*end;            // decrease to zero
        return next(begin, end);   // RECURSE!
    }
}

int main()
{
    char test[] = "0000";
    do
    {
        std::cout << test << std::endl;
    } while (next(test + 0, test + 4));
}

The program works with any sequence of any type. If you need all possible combinations at the same time, just put them into a collection instead of printing them out. Of course you need a different element type, because you cannot put C arrays into a vector. Let's use a vector of strings:

#include <string>
#include <vector>

int main()
{
    std::vector<std::string> combinations;
    std::string test = "0000";
    do
    {
        combinations.push_back(test);
    } while (next(test.begin(), test.end()));
    // now the vector contains all pssible combinations
}

If you don't like recursion, here is an equivalent iterative solution:

template <typename Iter>
bool next(Iter begin, Iter end)
{
    while (begin != end)       // we're not done yet
    {
        --end;
        if ((*end & 1) == 0)   // even number is treated as zero
        {
            ++*end;            // increase to one
            return true;       // still more numbers to come
        }
        else                   // odd number is treated as one
        {
            --*end;            // decrease to zero and loop
        }
    }
    return false;              // that was the last number
}

Interview question: C program to sort a binary array in O(n)

I see at least two problems in the program:

Problem 1:

last = arr + N;

is incorrect. It should be:

last = arr + N - 1;

because

(arr + 0) points to 0th ele
(arr + 1) points to 1st ele
...
(arr + N -1) points to (N-1)th ele..which is the last element.

Problem2:
Next your while loop:

while(front <= last)

is incorrect and should be:

while(front < last)

In your case when front and last become equal, your loop continues but
neither front nor last get modified at this point, resulting in infinite loop.

When front and last become equal, it makes no point to continue, your array
would have been sorted by then.

partial_sort not working correctly for vector

Take a look at what std::partial_sort() does:

Rearranges elements such that the range [first, middle) contains the sorted middle - first smallest elements in the range [first, last).

In other words, the partitioning you did is ignored.

There are a few alternatives:

1. std::sort() it all, and std::rotate() the zeroes to the end.

2. Sort it all with a custom comparator considering zero the biggest value.

3. std::partition() the range so zeroes are at the end, and then sort the front.

How to remove zero values from an array in parallel

To eliminate some elements from an array you may use Thrust Library's reordering operations. Given a predicate is_not_zero, which returns false for zero values, and true for others, you may write the operation like this

thrust::copy_if(in_array, in_array + size, out_array, is_not_zero);

the output array will include only the values which are non-zero, because the predicate indicates so.

You may also use "remove_if" function with a reverse predicate which return true for zeros, and false for others..

thrust::remove_if(in_array, in_array + size, is_zero);

I suggest you taking a look at compaction examples of Thrust library, or general compaction concept.

https://github.com/thrust/thrust/blob/master/examples/stream_compaction.cu

---

Related Topics