Abstract / Summary

Count pairs where the sum of their values is even and both values are in the given list.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 53% (90k+ submissions).

Typical patterns to solve this problem:

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

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method countBeautifulPairs that receives a list of integers and returns the number of index pairs (i, j) with i < j for which the greatest common divisor of the first digit of nums[i] and the last digit of nums[j] equals 1. The algorithm proceeds in three logical phases: extraction of digit information, pairwise evaluation, and accumulation of the result.

Extraction of first and last digits

The first phase converts each integer in the input list into its leading and trailing decimal digits. Two list comprehensions are used, each invoking str on the integer, indexing the appropriate character, and converting it back to an integer.

a = [int(str(n)[0]) for n in nums]
b = [int(str(n)[-1]) for n in nums]

The list a holds the first digit of every element, while b holds the last digit. By performing this work up-front, the later nested loops avoid repeated string conversions, which would otherwise dominate the runtime for large inputs.

Pairwise evaluation

The second phase iterates over all unordered pairs of positions where the first index is smaller than the second. The outer loop runs over the index of the first digit list, and the inner loop starts one position ahead in the last-digit list, guaranteeing i < j.

for i in range(len(a)):
    for j in range(i + 1, len(b)):
        if gcd(a[i], b[j]) == 1:
            result += 1

Inside the inner loop the built-in gcd function (from the math module) computes the greatest common divisor of the two digits. When the divisor equals 1, the pair satisfies the “beautiful” condition and the counter result is incremented.

Edge-case handling

The code naturally accommodates several boundary conditions without additional checks. When the input list is empty or contains a single element, the outer loop executes zero or one iteration, but the inner loop never finds a valid j because i + 1 exceeds the list length. Consequently, the method returns the initial value 0, correctly indicating that no pairs exist.

For numbers consisting of a single digit, the string representation has length 1, so both str(n)[0] and str(n)[-1] refer to the same character. The conversion yields identical first and last digits, and the algorithm still processes them correctly.

Because the digits are extracted as integers, any non-negative integer, regardless of magnitude, is reduced to a single-digit value for the gcd check. Negative numbers are not typical in this context, but the conversion to string preserves the leading minus sign; however, indexing [0] would capture '-', causing a ValueError on int. The code assumes the input conforms to the expected non-negative domain, which is consistent with typical problem constraints.

Performance optimizations

The most notable optimization is the separation of digit extraction from the pairwise comparison. By building the a and b arrays once, the algorithm eliminates the need to repeatedly convert integers to strings inside the double loop. This reduces the overhead from O(n²) string operations to O(n) preprocessing plus O(n²) integer gcd checks.

Using the standard library’s gcd function leverages a highly tuned implementation of the Euclidean algorithm, which is faster than a custom loop for small integers such as single digits. The inner condition gcd(a[i], b[j]) == 1 therefore executes efficiently.

The loop bounds range(i + 1, len(b)) ensure that each unordered pair is examined exactly once, avoiding duplicate work and unnecessary comparisons. The variable result is updated in place, avoiding the creation of intermediate collections.

Imagine a line of toys placed in a row. Each toy has a number written on it. To find something special, look at the very first number on each toy and the very last number on each toy.

The code starts by making two new lists. One list saves only the first digit of every toy, and the other list saves only the last digit.

Next, the computer picks two toys to look at side by side. It compares the first digit of the first toy with the last digit of the second toy. It asks a math machine if these two numbers share any special patterns. If the math machine says the only thing they share is the number one, then those two toys make a beautiful pair.

The computer keeps checking every possible pair of toys from the line. Every time it finds a beautiful pair, it adds a point to a growing total count. It keeps going until it has checked every single combination possible.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Java			C++		Python	TS
	WalkCCC	Java			C++		Python
	leetcode.ca	Java			C++	Go	Python	TS
	Progiez	Java			C++		Python
github	charles-wangkai	Java
	fsq		Rust
	JoshCrozier			JS
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	Rust
JoshCrozier	JavaScript
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality