Given an array arr[ ] of N non-negative integers, the task is to sort these integers according to sum of their digits.
Examples :
Input : 12 10 102 31 15 Output : 10 102 12 31 15 Input : 12 10 14 31 15 199 Output : 10 12 31 14 15 199 12 => 1 + 2 = 3 10 => 1 + 0 = 1 14 => 1 + 4 = 5 31 => 3 + 1 = 4 15 => 1 + 5 = 6 199 => 1 + 9 + 9 = 19
Approach :
The idea is to store the numbers with its sum of digits in an array of structures. And then sort all the elements according to their sum of digits using the qsort() function. At last print the sorted elements of the array. qsort() is defined in stdlib.h.
This is how to store the integers with the sum of the digits.
Below is the implementation of the approach:
//C implementation of the approach.
#include <stdio.h>
#include<stdlib.h>
// Structure definition.
typedef struct {
int number; // to store number.
int digitsum;// to store sum of digits.
} Digit;// User defined data type.
//Function to calculate and return the
//sum of the digits of the number.
int getDigitSum(int num)
{
int digit, sum = 0;
while(num != 0){
digit = num % 10;
num = num / 10;
sum += digit;
}
return sum;
}
// Compare function to use in qsort().
//default declaration of comparator function.
int cmp (const void *arg1, const void *arg2){
Digit* a = (Digit*) arg1;
Digit* b = (Digit*) arg2;
return a->digitsum - b->digitsum;
}
// implementation of code in main().
int main() {
// code
int num; // number of the integers.
//Ask the user to input the number
//of integers to be sorted.
num = 5;
// Ask the user to input the integers.
int a[] = {12, 10, 102, 31, 15};
//Declare an array of 'num' elements
//of pre-defined data type 'Data'.
Digit arr[num];
int i; //to interate in for loop.
// Store the integer in arr[i].number.
for(i = 0; i < num; i++)
arr[i].number = a[i];
// for loop to store the sum of
//digits of the corresponding numbers.
for(i = 0; i < num; i++){
arr[i].digitsum = getDigitSum(arr[i].number);
}
// Using qsort() to sort the numbers
//according to their sum of digits.
qsort(arr, num, sizeof(Digit), cmp);
// A simple for loop to print the sorted numbers.
for(i = 0; i < num; i++){
printf("%d ", arr[i].number);
}
return 0;
}
Output :
10 102 12 31 15
Time complexity: O(nlogn)
Space complexity: O(n)
Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.