Distinct Length Pairs

Count the number of pairs formed by selecting one integer from each of two lists where the integers have different numbers of digits.

Understand the Problem

Problem Statement

The program must accept M integers and N integers as the input. The program must form pairs of integers by selecting one integer from M integers and another integer from N integers. Then the program must print the number of pairs containing two integers with different number of digits as the output.

Constraints

1 ≤ M, N ≤ 10⁴
1 ≤ Each integer value ≤ 10¹⁶

Examples

Example 1

Input

3 4
12 1 454
988 2 112 47

Output

Explanation

The pairs with different length integers are: 12 (2 digits) with 988, 2, 112 (3 digits each) 1 (1 digit) with 988, 112, 47 (3 digits each) 454 (3 digits) with 2, 47 (1 and 2 digits respectively) Total: 8 pairs

Example 2

Input

5 10
464 69 1 9 62
69 26 592 28 22 252 172 341 9 5

Output

Explanation

After calculating digit counts and applying the efficient counting approach, we find that 34 out of the 50 possible pairs have integers with different numbers of digits.

Solution

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

// Function to count digits in a number
int countDigits(long long num) {
    int count = 0;
    do {
        count++;
        num /= 10;
    } while (num != 0);
    return count;
}

// Comparison function for qsort
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int M, N;
    scanf("%d %d", &M, &N);
    
    long long arr1[M], arr2[N];
    int digits1[M], digits2[N];
    
    // Read first array and calculate digit counts
    for (int i = 0; i < M; i++) {
        scanf("%lld", &arr1[i]);
        digits1[i] = countDigits(arr1[i]);
    }
    
    // Read second array and calculate digit counts
    for (int i = 0; i < N; i++) {
        scanf("%lld", &arr2[i]);
        digits2[i] = countDigits(arr2[i]);
    }
    
    // Sort both digit count arrays
    qsort(digits1, M, sizeof(int), compare);
    qsort(digits2, N, sizeof(int), compare);
    
    // Count pairs with different digit counts
    int count = 0;
    for (int i = 0; i < M; i++) {
        // Count how many in digits2 have different digit count than digits1[i]
        int sameCount = 0;
        for (int j = 0; j < N; j++) {
            if (digits2[j] == digits1[i]) {
                sameCount++;
            }
        }
        count += (N - sameCount);
    }
    
    printf("%d\n", count);
    return 0;
}

Time:O(M log M + N log N) - due to sorting the digit count arrays

Space:O(M + N) - for storing the digit count arrays

Approach:

C Solution Explanation:

Digit Counting: The countDigits function uses repeated division by 10 to count digits in each number.
Input Reading: We read both arrays and simultaneously calculate digit counts for each element.
Sorting: We sort both digit count arrays using qsort for efficient comparison.
Counting Logic: For each digit count in the first array, we count how many elements in the second array have the same digit count, then subtract from total to get different digit count pairs.
Output: Print the total count of pairs with different digit lengths.

Visual Explanation

Loading diagram...

All Problems