Abstract / Summary

Find the largest number that divides all elements of an array without a remainder.

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

Typical patterns to solve this problem:

• Array
• 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 implementation defines a single method findGCD inside a Solution class. The method receives a list of integers, determines the smallest and largest values in that list, and returns the greatest common divisor (GCD) of those two extremes using the standard library gcd function.

Key Steps

Determining the Minimum Value

The expression min(nums) scans the entire input list to locate the smallest element. This built-in function is implemented in C, providing a fast linear pass over the data.

minimum = min(nums)

Determining the Maximum Value

Similarly, max(nums) performs a linear scan to find the largest element in the list. Like min, it benefits from a highly optimized C implementation.

maximum = max(nums)

Computing the Greatest Common Divisor

The call gcd(minimum, maximum) invokes the Euclidean algorithm from the math module. This algorithm repeatedly replaces the larger number with the remainder of the division until the remainder becomes zero, at which point the non-zero operand is the GCD. The library version is written in C and therefore executes with minimal overhead.

result = gcd(minimum, maximum)

Returning the Result

The method returns the integer produced by the gcd call directly, completing the computation in a single return statement.

return result

Edge Cases Handled

When the input list contains a single element, both min(nums) and max(nums) yield the same value. The gcd of a number with itself is that number, so the method correctly returns the element as the GCD.

If all elements in the list are identical, the same reasoning applies: the minimum and maximum are equal, and the GCD equals that common value.

The built-in gcd function gracefully handles zero and negative inputs. If the list includes zero, the GCD of zero and another integer is the absolute value of the non-zero integer, which aligns with mathematical definitions. Negative numbers are treated by taking absolute values internally, ensuring the returned GCD is non-negative.

The method assumes a non-empty list, as calling min or max on an empty sequence would raise an exception. In typical usage scenarios where the input is guaranteed to contain at least one integer, this precondition is satisfied.

Performance Optimizations

The code leverages the Python standard library for all heavy lifting. Both min and max are executed in compiled C code, avoiding Python-level loop overhead. The gcd function also resides in the math module’s C implementation, providing a fast Euclidean algorithm without the cost of a Python-written loop.

By extracting only the extreme values from the list, the algorithm reduces the GCD computation to a single pair of numbers, regardless of the list’s length. This approach eliminates the need for pairwise GCD calculations across the entire array, which would be more computationally intensive.

Overall, the combination of linear scans for extremes and a constant-time GCD operation yields an efficient solution that scales well with input size while maintaining concise and readable code.

Imagine you have a big box of numbered blocks. Some of the numbers are very small, and some of the numbers are very tall. This code first looks for the smallest number in the box and puts it aside. Then, it looks for the biggest number in the box and puts that aside too. Once it has the teeny tiny number and the giant number, it plays a special game to see what is the largest number that can divide both of those chosen numbers perfectly. It is like finding a secret number that fits perfectly inside both the smallest and the biggest blocks at the same time.

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

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

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