Zeros and Ones .. One Pass

Have heard this question a lot and wanted to code it. I initially always used the version 1 (described below) of this code to form solutions, but I figured an optimization and the version 2 is actually a one-pass algorithm.

Version 1: ( debatable one pass)

#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n;
  cin >> n;
  // containing 0s and 1s
  vector<int> binaries;
  for (int i = 0, t = -1; i < n; ++i) {
    cin >> t;
    binaries.push_back(t);
  }

  vector<int>::iterator back_iter = binaries.begin();
  vector<int>::iterator front_iter = binaries.begin();

  for (; front_iter != binaries.end(); ++front_iter) {
    if (*front_iter == 0) {
      // find the localtion of the back pointer which is pointing to a 1
      while (back_iter != front_iter && *back_iter == 0) {
        ++back_iter;
      }
      if (back_iter != front_iter) {
        // found a place to replace
        iter_swap(back_iter, front_iter);
      }
    }
  }

  for (int i = 0; i < binaries.size(); ++i) {
    cout << binaries[i] << " ";
  }
  cout << "\n";
  return 0;
}

Version 2: Definitely one – pass 🙂

#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n;
  cin >> n;
  // containing 0s and 1s
  vector<int> binaries;
  for (int i = 0, t = -1; i < n; ++i) {
    cin >> t;
    binaries.push_back(t);
  }

  vector<int>::iterator front_iter = binaries.begin();
  vector<int>::iterator back_iter = binaries.end() - 1;

  for (; front_iter != binaries.end() && front_iter != back_iter; ) {
    if (*front_iter) {
      iter_swap(front_iter, back_iter);
      --back_iter;
    } else {
      ++front_iter;
    }
  }

  for (int i = 0; i < binaries.size(); ++i) {
    cout << binaries[i] << " ";
  }
  cout << "\n";
  return 0;
}

Finally I coded this. 😀

Advertisements

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

14 Responses to Zeros and Ones .. One Pass

  1. anuj says:

    Hi Avi

    You have really maintained a good collection of programming questions.
    One request kindly mention the resource from where you take the question along with the question(Though you have already done that at many places)
    Came across one more useful site like this : http://www.ihas1337code.com/

    Moreover ,I have collected few programming related books over time , want to share here :
    Two good books for interview preparation

    1)Cracking the Coding Interview by Gayle Laakmann
    2)Algorithms For Interviews by Adnan Aziz

    apart from this there are few other books that I have collected over time , they can be downloaded from this media fire link.
    http://www.mediafire.com/?rxpgur8pa2ccw

  2. Nitish Garg says:

    Hey anuj!
    The link you provided contains some very good programming books. Thanks for the link.
    But I am not able to download the book Algorithm for Interviews by Adnan Aziz. Can you please help?

  3. Nitish Garg says:

    Hey avi!
    Can you please explain the question to which you have provided the code?
    Thanks

  4. anuj says:

    @Nitish garg
    I have checked the link it’s working fine .I found it in one of google groups
    (http://groups.google.com/group/algogeeks/browse_thread/thread/c4a537922463ed50?pli=1 )
    Unfortunately it is removed from there due to copyright issue.

    • Nitish Garg says:

      If you have the ebook, can you please mail it to me. My email id is nitishgarg1991[at]gmail[dot]com.
      Thanks!
      PS: Sorry for spamming the comments section of your post avi!

  5. Pingback: Zeros and Ones .. One Pass | All kinds of ….solutions

  6. Oppilas says:

    Can you please include a link to the original question?

    • Avi Dullu says:

      I don’t have any link but the problem statement is to sort (and later stable sort) an array of 0s and 1s in a single pass. (Not using extra memory is implicit 🙂 )

  7. Abhishek says:

    Version 1 can be simple as below

    for (; front_iter != binaries.end(); ++front_iter) {
    if (*front_iter == 0) {
    if (back_iter != front_iter) {
    // found a place to replace
    iter_swap(back_iter, front_iter);
    }
    ++back_iter;
    }
    }

    Also version 2 is not working for 0 0 1 0 0 0

    • Avi Dullu says:

      Thanx Abhishek.
      Indeed it was not the best I wrote. I have updated the code, please re-check 🙂
      I only ran your code on 1 1 0 1 1 0 and it did not pass. Can you please confirm this and post again if you figure out the bug?
      Avi

      • Abhishek says:

        My code is working for 1 1 0 1 1 0 also. Below is the whole code which is copy paste of your version 1 code with my modifications in for loop. Please see if it breaks.

        #include <iostream>
        #include <vector>
        
        using namespace std;
        
        int main() {
          int n;
          cin >> n;
          // containing 0s and 1s
          vector<int> binaries;
          for (int i = 0, t = -1; i < n; ++i) {
            cin >> t;
            binaries.push_back(t);
          }
        
          vector<int>::iterator back_iter = binaries.begin();
          vector<int>::iterator front_iter = binaries.begin();
        
          for (; front_iter != binaries.end(); ++front_iter) {
            if (*front_iter == 0) {
                if (back_iter != front_iter) {
                  // found a place to replace
                   iter_swap(back_iter, front_iter);
                }
                ++back_iter;
            }
          }
          for (int i = 0; i < binaries.size(); ++i) {
            cout << binaries[i] << " ";
          }
          cout << endl;
          return 0;
        }
        
    • Avi Dullu says:

      Thanx. Your code is working.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: