Abstract / Summary

Count pairs of equal numbers in an array where one divides the other.

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 84% (200k+ submissions).

Typical patterns to solve this problem:

• Array

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 Solution class with a method countPairs that receives a list of integers nums and an integer k. Its purpose is to count the number of distinct index pairs (i, j) where i < j, the values at those indices are equal, and the product of the indices is divisible by k. The method returns this count as an integer.

Key Steps

The algorithm proceeds through three conceptual phases: initialization, pair enumeration, and result accumulation.

The first phase establishes a counter and determines the length of the input list.

result = 0
size = len(nums)

The second phase iterates over all possible ordered pairs of indices while ensuring each unordered pair is examined exactly once. The outer loop selects the first index i, and the inner loop selects the second index j starting from i + 1.

for i in range(size):
    for j in range(i + 1, size):

Within the nested loops, a conditional check verifies two criteria: the values at the two positions are identical, and the product i * j leaves no remainder when divided by k. If both conditions hold, the counter is incremented.

if nums[i] == nums[j] and (i * j) % k == 0:
    result += 1

The final phase simply returns the accumulated count.

return result

Edge Cases Handled

When the input list is empty, size becomes zero, causing both loops to be bypassed entirely. The method therefore returns the initial result value of zero, correctly indicating that no qualifying pairs exist.

If the list contains a single element, the outer loop executes once but the inner loop has no valid j values because i + 1 equals size. Again, the method returns zero, reflecting the impossibility of forming a pair.

The condition nums[i] == nums[j] ensures that only pairs of equal values contribute to the count. Consequently, lists with all distinct elements produce a result of zero regardless of the value of k.

When k is a divisor of the product of any two indices, the modulo expression evaluates to zero, satisfying the second part of the condition. The implementation therefore correctly includes such pairs, while pairs whose index product is not a multiple of k are excluded.

Performance Optimizations Observed

The algorithm avoids redundant pair examinations by starting the inner loop at i + 1. This design guarantees that each unordered pair (i, j) is considered exactly once and eliminates the need for additional checks to prevent double counting or self-pairing.

By performing the equality comparison nums[i] == nums[j] before the modulo operation, the code potentially reduces the number of expensive arithmetic operations. When the values differ, the modulo check is skipped entirely for that pair.

The use of simple integer arithmetic for the product and modulo calculation leverages the efficiency of native operations in the runtime environment, contributing to a straightforward and fast execution path for each examined pair.

Overall, the method delivers a clear and direct solution to the problem statement, systematically exploring all relevant index combinations while incorporating small but effective measures to keep the work per pair minimal.

Imagine you have a big box of colorful blocks with numbers written on them. You want to find pairs of blocks that match each other perfectly and follow a special secret rule. This code is like a little robot helper designed to look at every single block in the box.

The robot starts at the beginning of the line and picks up one block. Then, it walks down the line to compare that block with every other block it can find. First, it checks if the two blocks have the exact same number on them. If they do match, it checks the secret rule. The rule is that if you multiply the positions of those two blocks together, the result has to be a number that can be divided perfectly by another special number called k.

If the blocks have the same number and they pass the secret math test, the robot keeps track of that pair by keeping a running tally. It does this over and over again until it has checked every possible pair in the box. By the time the robot is finished looking at everything, it knows exactly how many pairs were lucky enough to follow both parts of the rule.

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	Python	C++	Java							TS
	WalkCCC	Python	C++	Java
	leetcode.ca	Python	C++	Java				Go	C	Rust	TS
	Progiez	Python	C++	Java
github	black-shadows		C++
	charles-wangkai			Java
	DimitrisJim	Python
	fartem					Ruby
	fsq		C++
	JoshCrozier						JS
	lkwq007	Python
	muhammadfarhankt							Go
	shreymehul				C#
	suxrobGM				C#
	trung-hn	Python
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	Python
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
muhammadfarhankt	Go
shreymehul	C#
suxrobGM	C#
trung-hn	Python
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