Friday, November 23, 2012

Given an array of positive integers, rearrange them so that they together form the largest number


#include<iostream>

#define SIZE 4
using namespace std;

bool decide(int a,int b)
{
int ta=a,tb=b;
int pa=1,pb=1;
while(a>0)
{
a/=10;
pa*=10;
}
while(b>0)
{
b/=10;
pb*=10;
}
int a_b=ta*pb+tb;//Append b after a.
int b_a=tb*pa+ta;//Append a after b.
if(a_b>b_a)
{
return false;
}
else
{
return true;
}
}

int main()
{
int A[SIZE]={87,181,9,5};
//Use any sorting technique but the decide function is the key.
for(int i=0;i<SIZE;i++)
{
for(int j=0;j<SIZE-i-1;j++)
{
if(decide(A[j],A[j+1]))
{
int t=A[j];
A[j]=A[j+1];
A[j+1]=t;
}
}
}
for(int i=0;i<SIZE;i++)
{
cout<<A[i]<<" ";
}
cout<<endl;
}
Input:
87 181 9 5
Output:
9 87 5 181

No comments:

Post a Comment