How to Solve Number of Beautiful Pairs

This problem requires scanning an integer array and checking all index pairs to see if the first digit of one number and the last digit of another are coprime. Using a hash table to store counts of last digits can reduce redundant gcd calculations. The result is the total number of such beautiful pairs in the array.

Problem Statement

Given a 0-indexed array of integers nums, define a pair of indices (i, j) as beautiful if 0 <= i < j < nums.length and the first digit of nums[i] is coprime with the last digit of nums[j].

Return the total number of beautiful pairs in nums. Two integers are coprime if their greatest common divisor is 1.

Examples

Example 1

Input: nums = [2,5,1,4]

Output: 5

There are 5 beautiful pairs in nums: When i = 0 and j = 1: the first digit of nums[0] is 2, and the last digit of nums[1] is 5. We can confirm that 2 and 5 are coprime, since gcd(2,5) == 1. When i = 0 and j = 2: the first digit of nums[0] is 2, and the last digit of nums[2] is 1. Indeed, gcd(2,1) == 1. When i = 1 and j = 2: the first digit of nums[1] is 5, and the last digit of nums[2] is 1. Indeed, gcd(5,1) == 1. When i = 1 and j = 3: the first digit of nums[1] is 5, and the last digit of nums[3] is 4. Indeed, gcd(5,4) == 1. When i = 2 and j = 3: the first digit of nums[2] is 1, and the last digit of nums[3] is 4. Indeed, gcd(1,4) == 1. Thus, we return 5.

Example 2

Input: nums = [11,21,12]

Output: 2

There are 2 beautiful pairs: When i = 0 and j = 1: the first digit of nums[0] is 1, and the last digit of nums[1] is 1. Indeed, gcd(1,1) == 1. When i = 0 and j = 2: the first digit of nums[0] is 1, and the last digit of nums[2] is 2. Indeed, gcd(1,2) == 1. Thus, we return 2.

Constraints

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 9999
• nums[i] % 10 != 0

Solution Approach

Brute-force pair checking

Iterate over all possible pairs of indices (i, j) with nested loops, extract the first digit of nums[i] and last digit of nums[j], and check gcd(first, last) == 1. Increment count for each beautiful pair.

Use digit frequency hash

Store a hash table mapping last digits to their counts as you scan the array. For each first digit, check only relevant last digits in the hash to compute coprime relationships, reducing redundant gcd checks.

Optimize with precomputed coprime table

Precompute a 10x10 boolean table for digits 1-9 indicating if two digits are coprime. Then count beautiful pairs by looking up table entries for first digits against existing last digits in the hash.

Complexity Analysis

Time complexity ranges from O(n^2) for naive pair checking to O(n) if using hash table with precomputed coprime relationships. Space complexity is O(10) for the digit frequency hash and coprime table.

What Interviewers Usually Probe

• Expecting you to notice nums.length is small and brute-force is feasible but can be optimized.
• Looking for awareness of coprime checking and avoiding repeated gcd calculations.
• Interested in using array scanning combined with hash lookup to efficiently count pairs.

Common Pitfalls or Variants

Common pitfalls

• Forgetting that only the first digit of nums[i] and last digit of nums[j] matter.
• Checking gcd for all pairs without using a hash leads to unnecessary repeated calculations.
• Mistakenly including pairs where i >= j or last digits are zero.

Follow-up variants

• Count beautiful pairs where first and last digits are multiples instead of coprime.
• Consider arrays with zeros and handle last digit extraction carefully.
• Extend to larger numbers or larger digit ranges requiring different hashing strategies.

How GhostInterview Helps

• Identifies exact array scanning plus hash lookup opportunities to efficiently count beautiful pairs.
• Highlights where repeated gcd computations can be avoided with precomputed tables or frequency maps.
• Guides on transforming problem constraints into actionable code optimizations for interview-ready solutions.

Topic Pages

• Array
• Hash Table
• Math
• Counting
• Number Theory

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is a beautiful pair in the Number of Beautiful Pairs problem?

A beautiful pair is a pair of indices (i, j) where i < j and the first digit of nums[i] is coprime with the last digit of nums[j].

Can I use a brute-force approach for this problem?

Yes, brute-force works for small arrays, but using a hash table for last digits and precomputed coprime table is faster.

How do I extract the first and last digits efficiently?

Last digit is nums[i] % 10. First digit can be found by dividing by 10 until the number is less than 10.

Why is the array scanning plus hash lookup pattern effective here?

It avoids repeated pairwise gcd calculations by counting last digits and referencing them for each first digit.

What constraints should I keep in mind for nums?

Array length is 2 to 100, nums[i] is 1 to 9999, and last digits are never zero, simplifying last digit extraction.