Number of Beautiful Pairs - Practice Coding Problems

Number of Beautiful Pairs - Problem

Array Hash Table Math Counting Number Theory Easy

You are given a 0-indexed integer array nums. A pair of indices (i, j) where 0 <= i < j < nums.length is called beautiful if the first digit of nums[i] and the last digit of nums[j] are coprime.

Return the total number of beautiful pairs in nums.

Two integers x and y are coprime if there is no integer greater than 1 that divides both of them. In other words, x and y are coprime if gcd(x, y) == 1, where gcd(x, y) is the greatest common divisor of x and y.

Input & Output

Example 1 — Basic Case

$ Input: nums = [11, 21, 22, 12]

› Output: 3

💡 Note: Beautiful pairs: (0,1) first=1,last=1 gcd=1; (0,2) first=1,last=2 gcd=1; (0,3) first=1,last=2 gcd=1

Example 2 — No Beautiful Pairs

$ Input: nums = [42, 21]

› Output: 0

💡 Note: Only pair (0,1): first=4, last=1, gcd(4,1)=1, so we have 1 beautiful pair

Example 3 — All Beautiful

$ Input: nums = [31, 25, 72, 18]

› Output: 5

💡 Note: Most pairs have coprime first and last digits: (0,1),(0,2),(0,3),(1,2),(2,3) are beautiful

Constraints

2 ≤ nums.length ≤ 100
1 ≤ nums[i] ≤ 9999

Visualization

Tap to expand

Understanding the Visualization

Input

Array of integers with first and last digits to check

Process

For each pair (i,j) where i<j, check if gcd(first[i], last[j]) = 1

Output

Count of all beautiful pairs found

Key Takeaway

🎯 Key Insight: A pair is beautiful when the first digit of nums[i] and last digit of nums[j] share no common factors except 1

Asked in

G Google 15 M Microsoft 12

The key insight is that two digits are coprime if their GCD equals 1. The brute force approach checks all pairs in O(n²) time, while the optimized approach uses a precomputed lookup table to avoid redundant GCD calculations. Best approach is frequency count optimization with Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count Optimization	O(n)	O(1)	Count occurrences of each first/last digit pair and use precomputed GCD table
Brute Force	O(n²)	O(1)	Check all pairs and calculate GCD for first and last digits

Frequency Count Optimization — Algorithm Steps

Count frequency of each first digit (1-9)
Count frequency of each last digit (0-9)
Use precomputed coprime table for digits
Multiply frequencies of coprime digit pairs

Visualization

Tap to expand

Step-by-Step Walkthrough

Precompute

Create coprime lookup table for all digit pairs

Extract

Get first and last digits for each pair

Lookup

Use table to instantly check if digits are coprime

Code -

solution.c — C

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

int getFirstDigit(int n) {
    if (n < 0) n = -n;
    while (n >= 10) {
        n /= 10;
    }
    return n;
}

int getLastDigit(int n) {
    if (n < 0) n = -n;
    return n % 10;
}

int solution(int* nums, int numsSize) {
    // Precomputed coprime table for digits 0-9
    bool coprime[10][10] = {
        {false, true, true, true, true, true, true, true, true, true},  // 0
        {true, true, true, true, true, true, true, true, true, true},   // 1
        {true, true, false, true, false, true, false, true, false, true}, // 2
        {true, true, true, false, true, true, false, true, true, false}, // 3
        {true, true, false, true, false, true, false, true, false, true}, // 4
        {true, true, true, true, true, false, true, true, true, false}, // 5
        {true, true, false, false, false, true, false, true, false, false}, // 6
        {true, true, true, true, true, true, true, false, true, true}, // 7
        {true, true, false, true, false, true, false, true, false, true}, // 8
        {true, true, true, false, true, true, false, true, true, false}  // 9
    };
    
    int count = 0;
    
    for (int i = 0; i < numsSize; i++) {
        int firstDigit = getFirstDigit(nums[i]);
        for (int j = i + 1; j < numsSize; j++) {
            int lastDigit = getLastDigit(nums[j]);
            if (coprime[firstDigit][lastDigit]) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple JSON array parsing
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int val = atoi(token);
        if (val != 0 || strcmp(token, "0") == 0) {
            nums[numsSize++] = val;
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count frequencies, then constant time to check all digit pairs

✓ Linear Growth

Space Complexity

O(1)

Fixed-size arrays for digit frequencies (at most 10 elements each)

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler