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
Approach:
- For each number, find all its divisors.
- If it has exactly 4 divisors, add their sum to the result.
- Return the total sum.
Key Logic:
- Loop from 1 to sqrt(n).
- If i divides n, both i and n/i are divisors.
- Use a counter to check if number has exactly 4 divisors.
- Use early exit if count > 4.
Time Complexity:
- For each number, divisor check takes O(sqrt(n)).
- Overall: O(n * sqrt(max(num)))
class Solution {
// Method to find the sum of divisors if a number has exactly 4 divisors
public static int divisor(int num) {
int count = 0; // To count the number of divisors
int sum = 0; // To keep track of sum of divisors
// Loop from 1 to sqrt(num)
for (int i = 1; i * i <= num; i++) {
if (num % i == 0) { // i is a divisor
int j = num / i; // j is the paired divisor
if (i == j) {
// If i and j are same (perfect square), add only once
count++;
sum += i;
} else {
// Add both i and j
count += 2;
sum += i + j;
}
}
// Early exit if divisors exceed 4
if (count > 4) return 0;
}
// Return sum only if there are exactly 4 divisors
return (count == 4) ? sum : 0;
}
// Main method to process an array and return total sum of numbers with exactly 4 divisors
public int sumFourDivisors(int[] nums) {
int totalsum = 0;
for (int num : nums) {
int sum = divisor(num); // Get sum of divisors (only if 4 divisors)
totalsum += sum; // Add to final result
}
return totalsum;
}
}
Comments
Post a Comment