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 😀

Advertisements

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

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: