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. 😀

Another simple solution

Am getting lesser and lesser time to maintain this blog 😦 .. anyways a friend of mine asked me a problem to solve recently and as soon as I got time (with some outside help :D) I was able to come to a very elegant looking simple solution. Sometimes we forget the basic properties of some algorithms which surprisingly can solve classic problems.

Problem: Given an array of elements find the largest possible number that can be formed by using the elements of the array.
eg: 10 9
ans: 910
eg: 2 3 5 78
ans: 78532

Solution:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

// Uncomment the commented code to see the behaviour

long long int NumberConcater(int a, int b) {
  char str_num[100];
  int sizea = sprintf(str_num, "%d", a);
  // cout << "1 : " << str_num;
  sprintf(str_num + sizea, "%d", b);
  // cout << "   2 : " << str_num;
  long long int option_number = atoll(str_num);
  // cout << "   Number : " << option_number << "\n";
  return option_number;
}
static bool MySorter(int a, int b) {
  long long int o1 = NumberConcater(a, b);
  long long int o2 = NumberConcater(b, a);
  return o1 > o2;
}

int main() {
  int n;
  cin >> n;
  vector<int> nums;
  for (int i = 0, t = 0; i < n; ++i) {
    cin >> t;
    nums.push_back(t);
  }
  sort(nums.begin(), nums.end(), MySorter);
  for (int i = 0; i < n; ++i) {
    cout << nums[i] << "\n";
  }
  return 0;
}

Using the concept of ordering, (I believe) this problem can be solved like this. Which is kinda cool 😀

%d bloggers like this: