Common Digits Count

Count the number of digits that appear in both of two given integers.

Understand the Problem

Problem Statement

The program must accept two integers X and Y as the input. The program must print the count of common digits in X and Y as the output.

Constraints

1 <= X, Y <= 10^8

Examples

Example 1

Input

5436
65547

Output

Explanation

The common digits in 5436 and 65547 are 5, 4, and 6. The digit 5 appears once in 5436 and twice in 65547, so we count 1. The digit 4 appears once in both, so we count 1. The digit 6 appears once in both, so we count 1. Total: 1 + 1 + 1 = 3.

Example 2

Input

22
22222

Output

Explanation

The only common digit is 2. It appears twice in the first number and five times in the second number. We count the minimum, which is 2.

Solution

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

int min(int a, int b) {
    return (a < b) ? a : b;
}

int countChar(const char *str, char c) {
    int count = 0;
    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] == c) {
            count++;
        }
    }
    return count;
}

int main() {
    char X[20], Y[20];
    fgets(X, sizeof(X), stdin);
    fgets(Y, sizeof(Y), stdin);
    
    // Remove newlines
    X[strcspn(X, "\n")] = 0;
    Y[strcspn(Y, "\n")] = 0;
    
    int total = 0;
    int used[10] = {0}; // To track which digits we've already counted
    
    for (int i = 0; X[i] != '\0'; i++) {
        char digit = X[i];
        if (isdigit(digit) && !used[digit - '0']) {
            used[digit - '0'] = 1;
            if (strchr(Y, digit) != NULL) {
                int countX = countChar(X, digit);
                int countY = countChar(Y, digit);
                total += min(countX, countY);
            }
        }
    }
    
    printf("%d\n", total);
    return 0;
}

Time:O(n * m) where n and m are the lengths of the input strings

Space:O(1) - uses a fixed-size array of 10 integers for tracking

Approach:

1. Read both input strings X and Y using fgets().
2. Remove trailing newlines from both strings.
3. Initialize a total counter and an array used to track which digits (0-9) have been processed.
4. Iterate through each character in X. For each digit character that hasn't been processed:
- Mark it as used in the used array.
- Check if this digit exists in Y using strchr().
- If it exists, count occurrences in both strings using the helper function countChar().
- Add the minimum of the two counts to total.
5. Print the final total.

Visual Explanation

Loading diagram...

All Problems