/*
Reference
https://helloacm.com/c-coding-exercise-largest-number-greedy/ :
"""
Arrange a list of non negative integers such that they form the largest
number. For example, given [3, 30, 34, 5, 9], the largest formed number
is 9534330. The result may be very large, so you need to return a string
instead of an integer.
Greedy Algorithm
The Greedy Algorithm (GA) always choose the best at the current iteration.
Given two numbers a and b, we pick the larger number if the string
concatenation of a+b is bigger than b+a, for example, 34, 5 we pick 5
because 534 is bigger than 345. 90 and 180 we pick 90 because 90180 is
bigger than 18090.
So, we know to to compare two numbers, in this customize way. We can
create a sort function comparator (has to be static in C++) and use the
STL:sort function to sort the numbers in the non-descending order. Adding
these numbers (in string format) one by one.
If all numbers are zero, we need to return “0”.
public:
static bool sortfunc(int a, int b) {
return to_string(a) + to_string(b) > to_string(b) + to_string(a);
}
string largestNumber(vector& nums) {
sort(nums.begin(), nums.end(), sortfunc);
string r = "";
for (auto num: nums) {
r += to_string(num);
}
return r[0] == '0' ? "0" : r;
}
};
"""
Task:
Write a main and a function doing the same as similar as possible, in C.
:-) DONE !
Compile:
$ gcc LargestNum.c -o /tmp/LargestNum -Wall
$
Run:
$ /tmp/LargestNum 5
3
30
34
5
9
9534330
$
License:
Copyright (C) 2016 Ch Iossif - chiossif@yahoo.com
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see .
*/
#include
#include
#include
int sortfunc(const void *a, const void *b){
static char stra[BUFSIZ];
static char strb[BUFSIZ];
static char sumab[BUFSIZ];
static char sumba[BUFSIZ];
sumab[0]=0;
sumba[0]=0;
sprintf(stra,"%d",*(const int *)a);
sprintf(strb,"%d",*(const int *)b);
strcat(sumab,stra);
strcat(sumab,strb);
strcat(sumba,strb);
strcat(sumba,stra);
return atoi(sumab)