We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Four Divisors

Number: 1284

Difficulty: Medium

Paid? No

Companies: Capital One

Problem Description

Given an integer array nums, the goal is to return the sum of divisors of the integers in that array that have exactly four divisors. If an integer does not have exactly four divisors, it should be ignored. In case no integer in the array meets this criterion, return 0.

Key Insights

  • An integer with exactly four divisors typically has the structure of two distinct prime factors (p * q), resulting in divisors: 1, p, q, and p*q.
  • To identify the divisors, iterate from 1 to the square root of the number, and count factors carefully (adding the complementary divisor when necessary).
  • If a divisor is encountered twice (as in a perfect square), count it only once.
  • If the count of divisors exceeds four during the process, you can break early to save time.

Space and Time Complexity

Time Complexity: O(n * sqrt(max_num)) where n is the length of the nums array and max_num is the maximum value in nums (up to 10^5).
Space Complexity: O(1), aside from the space required for the input.

Solution

The solution iterates over every integer in the input array and checks its divisors using a loop from 1 to the square root of the number. For each divisor i found, if i divides the number, we consider both i and the quotient (number / i) unless they are the same. We count these divisors and sum them up as we go. If at any point the divisor count exceeds four, we discontinue checking further for that number. Only when exactly four divisors have been found do we add the sum of these divisors to our final result. This approach allows us to efficiently handle numbers up to 10^5 given the problem constraints.

Code Solutions

# Python solution
def sumFourDivisors(nums):
    total_sum = 0  # This will store the final sum of divisors for numbers with exactly four divisors
    # Iterate over each number in the list
    for num in nums:
        divisors_sum = 0  # Sum of the divisors for the current number
        count = 0  # Counter for number of divisors found
        # Loop from 1 to the square root of num
        i = 1
        while i * i <= num:
            if num % i == 0:  # If i is a divisor
                quotient = num // i
                # If both divisors are the same (perfect square), count only once
                if i == quotient:
                    count += 1
                    divisors_sum += i
                else:
                    count += 2
                    divisors_sum += i + quotient
            # Early exit if more than 4 divisors are found
            if count > 4:
                break
            i += 1
        # If exactly 4 divisors, add the sum of these divisors to the total sum
        if count == 4:
            total_sum += divisors_sum
    return total_sum

# Example usage:
# print(sumFourDivisors([21,4,7]))  # Expected output: 32
← Back to All Questions