CODEWITHSUNDEEP
c++algorithmoptimization
Premature Optimizer
Premature Optimizer

Reputation: 237

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

I'm trying to write the fast and coolest solution to the problem of bringing all the ones to the front of an array of zeros and ones.

I wrote this: 

void zeros_to_front(char * c, int n)
{
   char * lastPtr(c);
   for (char * thisCharPtr(c), * endCharPtr(c+n+1); thisCharPtr != endCharPtr; ++thisCharPtr)
   {
      if (*thisCharPtr == '1')
      {
         *lastPtr = '1';
         *thisCharPtr = '0';
          ++lastPtr;
      }
   }
}

int main()
{

   char thisArray[] = {'0', '0', '1', '0', '1', '1', '1'};
   int len = sizeof(thisArray)/sizeof(char);
   zeros_to_front(thisArray, len);
   for (int i = 0; i < len; ++i)
      std::cout << thisArray[i] << " ";

    return 0;
}

A few questions:

Upvotes: 3

Views: 144

Answers (4)

Pham Trung
Pham Trung

Reputation: 11294

This solution will require 1 pass in the array and space O(n). The final result is stored in array result

 void cal(int *data , int* result , int n) {
      int index = n - 1;
      for(int i = 0; i < n; i++){
         if(data[i] == 1){
             result[index--] = 1;
         } 
      } 
  }

Upvotes: 1

Blastfurnace
Blastfurnace

Reputation: 18652

This version takes the same form as cmasters' but might be faster depending on your standard library implementation. I know Visual C++ will turn each of these std::fill calls into a memset().

void zero_to_front(char* c, int n)
{
    size_t ones = std::count(c, c + n, '1');
    std::fill(c, c + ones, '1');
    std::fill(c + ones, c + n, '0');
}

Upvotes: 3

cmaster - reinstate monica
cmaster - reinstate monica

Reputation: 40655

The fastest way to do this is the two pass counting approach. Why? Because it eliminates the need for a condition in the inner loop, which is expensive. Here is the code:

void zerosToFront(char* c, size_t n) {
    size_t oneCount = 0, i;
    for(i = 0; i < n; i++) oneCount += c[i];
    for(i = 0; i < n - oneCount; i++) c[i] = 0;
    for(     ; i < n; i++) c[i] = 1;
}

Upvotes: 3

user2481909
user2481909

Reputation: 386

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)

Upvotes: 2

Related Questions