Count of Inversions – Base 6 – TCS CodeVita

Count inversions in a derived sequence formed by sum of digits in base 6 representation

Understand the Problem

Problem Statement

Given a sequence of distinct numbers a₁, a₂, … a_n, an inversion occurs if there are indices i < j such that a_i > a_j.

From the main sequence, create a derived sequence where each element is the sum of digits in the base 6 representation of the corresponding number in the main sequence. Return the number of inversions in this derived sequence.

For example, for number 1409, the base 6 representation is 10305, and the sum of digits is 1+0+3+0+5 = 9.

Constraints

2 ≤ N ≤ 100
Each integer value ≤ 10^7
All integers are distinct and positive
Derived sequence values are sum of base 6 digits

Examples

Example 1

Input

5
62,85,44,21,36

Output

Explanation

Base 6 representations: 62→142, 85→221, 44→112, 21→33, 36→100. Derived sequence: [7, 5, 4, 6, 1]. Inversions: (7,5), (7,4), (7,6), (7,1), (5,4), (5,1), (4,1), (6,1) = 8 total.

Example 2

Input

8
39,46,999,22,19,136,91,81

Output

Explanation

Derived sequence: [4, 6, 14, 7, 4, 11, 6, 6]. There are 11 inversions where earlier elements are greater than later elements.

Solution

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

int sumOfBase6Digits(int num) {
    int sum = 0;
    while (num > 0) {
        sum += num % 6;
        num /= 6;
    }
    return sum;
}

int countInversions(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] > arr[j]) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int* derived = (int*)malloc(n * sizeof(int));
    
    for (int i = 0; i < n; i++) {
        int num;
        scanf("%d", &num);
        derived[i] = sumOfBase6Digits(num);
    }
    
    int result = countInversions(derived, n);
    printf("%d", result);
    
    free(derived);
    return 0;
}

Time:O(N²)

Space:O(N)

Approach:

1. sumOfBase6Digits(): Extracts digits in base 6 using modulo 6 and division operations, summing them.

2. countInversions(): Uses nested loops to compare all pairs (i, j) where i < j, counting inversions.

3. main(): Reads input, converts each number to base 6 digit sum, stores in derived array, then counts inversions.

4. Uses dynamic memory allocation and proper cleanup.

Visual Explanation

Loading diagram...

All Problems