Sort based on Weight

Sort N integers based on their computed weight, where weight is determined by perfect square, multiple of 4 and divisible by 6, and even number conditions

Understand the Problem

Problem Statement

The program must accept N integers as the input. For each integer X, the program must find the sum of the weights based on the following conditions:
– If X is a perfect square then the weight is 5.
– If X is a multiple of 4 and divisible by 6 then the weight is 4.
– If X is an even integer then the weight is 3.
– Else the weight of X is 0.
The program must print the integers with their weight as the output. The integers are sorted based on their weight in ascending order. If more than one integers have the same weight then print those integers in the order of their occurrence.

Constraints

1 ≤ N ≤ 1000
1 ≤ Each integer value ≤ 10^4
Weights are calculated based on cumulative conditions (multiple conditions can apply to same number)
Output must maintain original order for integers with same weight

Examples

Example 1

Input

6
10 36 54 89 12 17

Output

Explanation

• 89: Not perfect square, not multiple of 4÷6, not even → weight = 0 • 17: Not perfect square, not multiple of 4÷6, not even → weight = 0 • 10: Not perfect square, not multiple of 4÷6, but even → weight = 3 • 54: Not perfect square, not multiple of 4÷6, but even → weight = 3 • 12: Not perfect square, but multiple of 4÷6 AND even → weight = 4 + 3 = 7 • 36: Perfect square (6²), multiple of 4÷6, AND even → weight = 5 + 4 + 3 = 12

Example 2

Input

5
37 121 11 81 71

Output

Explanation

• 37, 11, 71: None of the conditions apply → weight = 0 • 121: Perfect square (11²), not multiple of 4÷6, not even → weight = 5 • 81: Perfect square (9²), not multiple of 4÷6, not even → weight = 5

Solution

#include <stdio.h>
#include <math.h>

struct Number {
    int value;
    int weight;
    int index;
};

int isPerfectSquare(int n) {
    int root = sqrt(n);
    return (root * root == n);
}

int compare(const void *a, const void *b) {
    struct Number *num1 = (struct Number *)a;
    struct Number *num2 = (struct Number *)b;
    
    // Primary sort by weight
    if (num1->weight != num2->weight) {
        return num1->weight - num2->weight;
    }
    // Secondary sort by original index (stability)
    return num1->index - num2->index;
}

int main() {
    int n;
    scanf("%d", &n);
    
    struct Number numbers[n];
    
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        
        int weight = 0;
        
        // Check perfect square
        if (isPerfectSquare(x)) {
            weight += 5;
        }
        
        // Check multiple of 4 and divisible by 6
        if (x % 4 == 0 && x % 6 == 0) {
            weight += 4;
        }
        
        // Check even number
        if (x % 2 == 0) {
            weight += 3;
        }
        
        numbers[i].value = x;
        numbers[i].weight = weight;
        numbers[i].index = i;
    }
    
    // Sort by weight, then by original index
    qsort(numbers, n, sizeof(struct Number), compare);
    
    // Output results
    for (int i = 0; i < n; i++) {
        printf("%d %d\n", numbers[i].value, numbers[i].weight);
    }
    
    return 0;
}

Time:O(N log N) - due to sorting, where N is the number of integers

Space:O(N) - for storing the array of structures

Approach:

The C solution uses a structure to store each number with its weight and original index. The algorithm:

1. Structure Definition: struct Number holds value, weight, and original index.

2. Perfect Square Check: The isPerfectSquare() function calculates the square root and checks if squaring it gives back the original number.

3. Weight Calculation: For each number, we check all three conditions and accumulate the weight accordingly.

4. Stable Sorting: Uses qsort() with a custom comparator that sorts primarily by weight, and secondarily by original index to maintain stability.

5. Output: Prints each number followed by its weight in the sorted order.

Visual Explanation

Loading diagram...

All Problems