Customers Group – Purchase Amount

Group customers by purchase amount in descending order and sort names within each group

Understand the Problem

Problem Statement

Customers Group – Purchase Amount: In a pantry, N customers have purchased the items they need. The name of each customer and his/her total purchase amount A are passed as the input to the program. The program must group the customers based on the purchase amount (i.e., the customers with the same purchase amount belong to one group). The program must print the purchase amount and the names of the customers belonging to each group as the output. The purchase amounts must be printed in descending order. In each group, the names of the customers must be printed in sorted order.

Constraints

1 ≤ N ≤ 50
1 ≤ Length of customer's name ≤ 20
10 ≤ A ≤ 10^5
Customer names contain only alphabets and spaces
All purchase amounts are positive integers

Examples

Example 1

Input

5
ghi 1500
def 1200
abc 1500
jkl 1500
mno 1600

Output

1600 mno
1500 abc, ghi, jkl
1200 def

Explanation

The purchase amounts in descending order are 1600, 1500 and 1200. There is only one customer (mno) with purchase amount 1600. There are three customers (abc, ghi, jkl) with purchase amount 1500, sorted alphabetically. There is only one customer (def) with purchase amount 1200.

Example 2

Input

4
abcd 950
Efg 2700
PQR 950
mno 950

Output

2700 Efg
950 PQR, abcd, mno

Explanation

The purchase amounts in descending order are 2700 and 950. There is only one customer (Efg) with purchase amount 2700. There are three customers (abcd, mno, PQR) with purchase amount 950, sorted alphabetically.

Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Structure to store customer data
struct Customer {
    char name[21];
    int amount;
};

// Structure to store grouped data
struct Group {
    int amount;
    char names[50][21];  // Maximum 50 customers
    int count;
};

// Comparison function for sorting customers by amount (descending)
int compare_amounts(const void *a, const void *b) {
    return ((struct Customer *)b)->amount - ((struct Customer *)a)->amount;
}

// Comparison function for sorting strings alphabetically
int compare_strings(const void *a, const void *b) {
    return strcmp((char *)a, (char *)b);
}

int main() {
    int n;
    scanf("%d", &n);
    getchar(); // consume newline
    
    struct Customer customers[50];
    struct Group groups[50];
    int group_count = 0;
    
    // Read input
    for (int i = 0; i < n; i++) {
        fgets(customers[i].name, 21, stdin);
        // Remove newline if present
        int len = strlen(customers[i].name);
        if (customers[i].name[len-1] == '\n') {
            customers[i].name[len-1] = '\0';
        }
        
        // Parse amount from the end of the string
        char *space = strrchr(customers[i].name, ' ');
        customers[i].amount = atoi(space + 1);
        *space = '\0';
    }
    
    // Group customers by amount
    for (int i = 0; i < n; i++) {
        int found = 0;
        
        // Check if this amount already exists in groups
        for (int j = 0; j < group_count; j++) {
            if (groups[j].amount == customers[i].amount) {
                strcpy(groups[j].names[groups[j].count], customers[i].name);
                groups[j].count++;
                found = 1;
                break;
            }
        }
        
        // If not found, create new group
        if (!found) {
            groups[group_count].amount = customers[i].amount;
            strcpy(groups[group_count].names[0], customers[i].name);
            groups[group_count].count = 1;
            group_count++;
        }
    }
    
    // Sort groups by amount (descending)
    for (int i = 0; i < group_count - 1; i++) {
        for (int j = 0; j < group_count - i - 1; j++) {
            if (groups[j].amount < groups[j+1].amount) {
                struct Group temp = groups[j];
                groups[j] = groups[j+1];
                groups[j+1] = temp;
            }
        }
    }
    
    // Sort names within each group and print results
    for (int i = 0; i < group_count; i++) {
        qsort(groups[i].names, groups[i].count, 21, compare_strings);
        
        printf("%d %s", groups[i].amount, groups[i].names[0]);
        for (int j = 1; j < groups[i].count; j++) {
            printf(", %s", groups[i].names[j]);
        }
        printf("\n");
    }
    
    return 0;
}

Time:O(N log N + G * C log C) where N is total customers, G is number of groups, and C is average customers per group

Space:O(N) for storing customer data and groups

Approach:

C Solution Explanation:

Structure Definition: We define two structures: Customer to store individual customer data and Group to store grouped data with amount and list of names.
Input Reading: We read each line, parse the customer name and purchase amount by finding the last space in the string.
Grouping Logic: For each customer, we check if their purchase amount already exists in our groups. If yes, we add their name to that group. If not, we create a new group.
Sorting Groups: We sort the groups by purchase amount in descending order using bubble sort.
Sorting Names: For each group, we sort the customer names alphabetically using qsort with string comparison.
Output: We print each group with the purchase amount followed by comma-separated sorted names.

Visual Explanation

Loading diagram...

All Problems