Jobs

Interviews

Discussions

Four Divisors

Medium

Capital One

0 views

Topics:

Arrays

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⁵

Four Divisors

Medium

Capital One

0 views

Topics:

Arrays

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⁵

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array `nums`?
Can the input array `nums` be empty or contain null values?
If no numbers in `nums` have exactly four divisors, what value should I return?
Are duplicate numbers allowed in the input array `nums`, and if so, should I calculate the sum of divisors for each occurrence, or only consider unique values?
Is there a specific data type I should use for the sum of divisors to prevent potential overflow issues, considering the possible range of divisor sums?

Brute Force Solution

Approach

The brute force approach to finding numbers with exactly four divisors means we'll examine each number individually. For each number, we will methodically check all possible numbers to see if they divide evenly into it. Finally, we will determine if it indeed has exactly four of these divisors.

Here's how the algorithm would work step-by-step:

Take the first number you want to check.
Start with the number one and see if it divides evenly into your number.
Continue checking every number, one by one, all the way up to your original number, to see if it divides evenly.
Count how many numbers divided evenly into your original number.
If the count is exactly four, then your original number is one of the numbers you are looking for.
Move on to the next number you want to check and repeat the process from the beginning.

Code Implementation

def sum_of_numbers_with_four_divisors(numbers):
    final_sum = 0

    for current_number in numbers:
        list_of_divisors = []

        # Find all divisors of the current number
        for i in range(1, current_number + 1):
            if current_number % i == 0:
                list_of_divisors.append(i)

        # Check if the current number has exactly four divisors
        if len(list_of_divisors) == 4:
            # Sum the divisors if the count is four
            divisor_sum = sum(list_of_divisors)

            # Add the sum to the final sum
            final_sum += divisor_sum

    return final_sum

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through each number in the input array (let's assume the largest possible value in the array is 'n'). For each number, it then iterates from 1 up to that number to count its divisors. In the worst case, for a number 'n', this inner loop runs 'n' times. Since this divisor-counting process is repeated for a number of times proportional to 'n', the total number of operations approximates n * n, thus the time complexity is O(n^2).

Space Complexity

O(1) – The brute force approach described only utilizes a few constant space variables. It needs a variable to store the current number being checked, a variable to count the divisors, and a few loop counters. The space required for these variables does not depend on the input number N, so the auxiliary space complexity is constant.

Optimal Solution

Approach

The key to efficiently finding numbers with exactly four divisors is understanding how divisors work. A number has exactly four divisors if it's either the product of two distinct prime numbers or the cube of a prime number.

Here's how the algorithm would work step-by-step:

For each number you're given, first check if it's less than 6 because numbers less than this can't have four divisors.
Next, try to find the divisors of the number. Instead of checking every number up to the number itself, you only need to check up to the square root of the number, which is a big shortcut.
As you find divisors, keep a count. If you find more than four divisors, you can stop checking because the number does not meet the requirements.
If you find exactly two divisors (other than 1 and the number itself), check if these two divisors are prime numbers. If they are both prime, then the number has exactly four divisors (1, prime1, prime2, and the number itself).
Alternatively, if you find only one divisor (other than 1), cube that divisor. If the result is equal to the original number, and if that divisor is prime, then the original number has exactly four divisors (1, prime, prime squared, and prime cubed).
If either of those two conditions are met, add the divisors (1, the prime divisors or the prime divisor and its square, and the number itself) to a sum.
Finally, after checking all the numbers, return the total sum.

Code Implementation

def sumFourDivisors(numbers):
    total_sum_of_divisors = 0

    def isPrime(number_to_check):
        if number_to_check <= 1:
            return False
        for i in range(2, int(number_to_check**0.5) + 1):
            if number_to_check % i == 0:
                return False
        return True

    for number in numbers:
        if number < 6:
            continue

        divisors = []
        first_prime_factor = -1

        # Finding the first prime factor is a key optimization
        for i in range(2, int(number**0.5) + 1):
            if number % i == 0:
                if isPrime(i):
                    first_prime_factor = i
                    break

        if first_prime_factor != -1:
            second_factor = number // first_prime_factor

            # Check for product of two distinct primes
            if isPrime(second_factor) and second_factor != first_prime_factor:
                divisors = [1, first_prime_factor, second_factor, number]
                total_sum_of_divisors += sum(divisors)
            else:
                # Verify if it could be a cube of a prime
                cube_root = round(number ** (1/3))
                if cube_root ** 3 == number and isPrime(cube_root):
                    divisors = [1, cube_root, cube_root * cube_root, number]
                    total_sum_of_divisors += sum(divisors)

    return total_sum_of_divisors

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n * sqrt(m)) – The algorithm iterates through an array of n numbers. For each number, it finds divisors up to the square root of that number (m), where m is the value of the number being checked. The primality check within the loop also contributes a factor related to the square root. Therefore, the dominant factor is the nested loop with a square root bound leading to O(n * sqrt(m)) time complexity where m is the maximum value in the input array.

Space Complexity

O(1) – The space complexity is O(1) because the algorithm uses a fixed number of variables to store the sum of divisors, a count of divisors, and potentially a few temporary variables within the loops and isPrime function. The number of these variables does not depend on the input array's size N. No auxiliary data structures that scale with the input size are used.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately, as there are no numbers to process.
Array containing numbers less than 1 (0 or negative numbers)	Ignore these numbers in the divisor calculation, as they cannot have exactly four divisors.
Large numbers in the input array exceeding integer limits for divisor sum	Use a 64-bit integer type (long) for accumulating the divisor sum to prevent overflow.
Numbers in the array that are perfect cubes of primes (e.g., 8 = 2^3)	The number of divisors is 4 (1, p, p^2, p^3), so calculate and include the sum of the divisors.
Numbers in the array that are the product of two distinct primes (e.g., 6 = 2*3)	The number of divisors is 4 (1, p, q, pq), so calculate and include the sum of the divisors.
Numbers in the array that have more than four divisors	Ensure the divisor counting logic correctly identifies and excludes these numbers.
Array with a large number of elements, impacting time complexity	Optimize divisor calculation to avoid unnecessary iterations, potentially up to the square root of the number.
Integer overflow during divisor product	Use long or appropriate data type to handle potential overflows in divisor product calculations.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array `nums`?
Can the input array `nums` be empty or contain null values?
If no numbers in `nums` have exactly four divisors, what value should I return?
Are duplicate numbers allowed in the input array `nums`, and if so, should I calculate the sum of divisors for each occurrence, or only consider unique values?
Is there a specific data type I should use for the sum of divisors to prevent potential overflow issues, considering the possible range of divisor sums?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number you want to check.
Start with the number one and see if it divides evenly into your number.
Continue checking every number, one by one, all the way up to your original number, to see if it divides evenly.
Count how many numbers divided evenly into your original number.
If the count is exactly four, then your original number is one of the numbers you are looking for.
Move on to the next number you want to check and repeat the process from the beginning.

Code Implementation

def sum_of_numbers_with_four_divisors(numbers):
    final_sum = 0

    for current_number in numbers:
        list_of_divisors = []

        # Find all divisors of the current number
        for i in range(1, current_number + 1):
            if current_number % i == 0:
                list_of_divisors.append(i)

        # Check if the current number has exactly four divisors
        if len(list_of_divisors) == 4:
            # Sum the divisors if the count is four
            divisor_sum = sum(list_of_divisors)

            # Add the sum to the final sum
            final_sum += divisor_sum

    return final_sum

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

For each number you're given, first check if it's less than 6 because numbers less than this can't have four divisors.
Next, try to find the divisors of the number. Instead of checking every number up to the number itself, you only need to check up to the square root of the number, which is a big shortcut.
As you find divisors, keep a count. If you find more than four divisors, you can stop checking because the number does not meet the requirements.
If you find exactly two divisors (other than 1 and the number itself), check if these two divisors are prime numbers. If they are both prime, then the number has exactly four divisors (1, prime1, prime2, and the number itself).
Alternatively, if you find only one divisor (other than 1), cube that divisor. If the result is equal to the original number, and if that divisor is prime, then the original number has exactly four divisors (1, prime, prime squared, and prime cubed).
If either of those two conditions are met, add the divisors (1, the prime divisors or the prime divisor and its square, and the number itself) to a sum.
Finally, after checking all the numbers, return the total sum.

Code Implementation

def sumFourDivisors(numbers):
    total_sum_of_divisors = 0

    def isPrime(number_to_check):
        if number_to_check <= 1:
            return False
        for i in range(2, int(number_to_check**0.5) + 1):
            if number_to_check % i == 0:
                return False
        return True

    for number in numbers:
        if number < 6:
            continue

        divisors = []
        first_prime_factor = -1

        # Finding the first prime factor is a key optimization
        for i in range(2, int(number**0.5) + 1):
            if number % i == 0:
                if isPrime(i):
                    first_prime_factor = i
                    break

        if first_prime_factor != -1:
            second_factor = number // first_prime_factor

            # Check for product of two distinct primes
            if isPrime(second_factor) and second_factor != first_prime_factor:
                divisors = [1, first_prime_factor, second_factor, number]
                total_sum_of_divisors += sum(divisors)
            else:
                # Verify if it could be a cube of a prime
                cube_root = round(number ** (1/3))
                if cube_root ** 3 == number and isPrime(cube_root):
                    divisors = [1, cube_root, cube_root * cube_root, number]
                    total_sum_of_divisors += sum(divisors)

    return total_sum_of_divisors

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately, as there are no numbers to process.
Array containing numbers less than 1 (0 or negative numbers)	Ignore these numbers in the divisor calculation, as they cannot have exactly four divisors.
Large numbers in the input array exceeding integer limits for divisor sum	Use a 64-bit integer type (long) for accumulating the divisor sum to prevent overflow.
Numbers in the array that are perfect cubes of primes (e.g., 8 = 2^3)	The number of divisors is 4 (1, p, p^2, p^3), so calculate and include the sum of the divisors.
Numbers in the array that are the product of two distinct primes (e.g., 6 = 2*3)	The number of divisors is 4 (1, p, q, pq), so calculate and include the sum of the divisors.
Numbers in the array that have more than four divisors	Ensure the divisor counting logic correctly identifies and excludes these numbers.
Array with a large number of elements, impacting time complexity	Optimize divisor calculation to avoid unnecessary iterations, potentially up to the square root of the number.
Integer overflow during divisor product	Use long or appropriate data type to handle potential overflows in divisor product calculations.