Is Four Divisors easy or hard?

Four Divisors is rated Medium because it requires recognizing divisor pair symmetry and limiting checks to √n. The coding itself is straightforward, but candidates must optimize the divisor search and handle edge cases like perfect squares correctly.

Four Divisors Python/Java solution

Both Python and Java implementations iterate through each number and check divisibility up to its square root. When a divisor pair is found, the algorithm updates the divisor count and sum, stopping early if the count exceeds four. The same logic translates directly to C++, JavaScript, and other languages.

How to solve Four Divisors in O(n)?

A strict O(n) solution is not typical without preprocessing. Most implementations check divisors up to √n for each number. With advanced preprocessing such as a sieve to identify primes and factorization patterns, you can reduce repeated work, but the standard accepted solution remains O(n * √m).

What is the best approach for Four Divisors?

The optimized divisor checking approach is the most practical. For each number, iterate only up to √n, count divisor pairs, and stop early once the count exceeds four. This avoids unnecessary checks for numbers that clearly have more than four divisors while keeping space usage constant.

Is Four Divisors asked at Google/Amazon/Meta?

Four Divisors is a medium-level problem commonly used in technical interview practice. Variants involving divisor counting and number properties appear in interviews at companies like Amazon and Google, especially when testing math reasoning and efficient iteration.

What data structure is used in Four Divisors?

The solution mainly relies on array traversal and mathematical divisor checks. No complex data structure is required. A few integer counters and accumulators track the number of divisors and their sum while scanning each value.

What is the time complexity of Four Divisors?

The typical solution runs in O(n * √m) time, where n is the number of elements in the array and m is the maximum value in the array. Each number requires checking potential divisors up to its square root. Space complexity remains O(1) because only counters and sums are stored.

1390. Four Divisors - Practice Online

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors. If there is no such integer in the array, return 0.

Example 1:

Input: nums = [21,4,7]
Output: 32
Explanation: 
21 has 4 divisors: 1, 3, 7, 21
4 has 3 divisors: 1, 2, 4
7 has 2 divisors: 1, 7
The answer is the sum of divisors of 21 only.

Example 2:

Input: nums = [21,21]
Output: 64

Example 3:

Input: nums = [1,2,3,4,5]
Output: 0

Constraints:

1 <= nums.length <= 10⁴
1 <= nums[i] <= 10⁵