Four Divisors

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
10 upvotes
Asked in company
Google inc

Problem statement

Ninja was planning to propose to his crush, Nina, with his spectacular martial arts moves. But Nina was more interested in numbers and divisors, so she gave Ninja a challenge to complete. If Ninja solves it, only then she will date him.

Nina gave him an array of positive integers, ‘ARR’ and asked him to find the sum of divisors of the integers in ‘ARR’ with exactly four divisors. In case there is no such integer with exactly four divisors, then the answer is 0. Ninja has been struggling for a very long time, so he needs your help to solve the problem.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains an integer ‘N’ representing the number of integers in the array, ‘ARR’.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the ‘ARR’ array.
Output Format: 
For each test case, return the sum of divisors of the integers in ‘ARR’ with exactly four divisors. In case there is no such integer with exactly four divisors, then return 0.

The output of each test case will be printed in a separate line.
Constraints: 
1 <= T <= 5
1 <= N <= 2000
1 <= ARR[ i ] <= 10 ^ 5

Where ‘T’ is the number of test cases, ‘N’ is the number of integers in the array, ‘ARR’ and ‘ARR[ i ]’ is the ‘i’th element in the ‘ARR’ array.

Time limit: 1 second
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1:
2
4
2 5 6 15
3
4 18 21
Sample Output 1:
36
32
Explanation of Sample Output 1:
Test Case 1 :  
Divisors of 2 are 1 and 2.
Divisors of 5 are 1 and 5.
Divisors of 6 are 1, 2, 3 and 6.
Divisors of 15 are 1, 3, 5 and 15.
Since 6 and 15 have exactly four divisors. Sum of their divisors is (1 + 2 + 3 + 6) + (1 + 3 + 5 + 15) = 36.

Test Case 2 : 
Divisors of 4 are 1, 2 and 4.
Divisors of 18 are 1, 2, 3, 6, 9 and 18.
Divisors of 21 are 1, 3, 7 and 21.
Since only 21 has exactly four divisors. Sum of its divisors is (1 + 3 + 7 + 21) = 32.
Sample Input 2:
2
5
7 35 64 11 8
6
27 13 42 25 25 25
Sample Output 2:
63
40
Hint

Use brute force approach and find divisors of each element in the array, ‘ARR’.

Approaches (2)
Brute Force

The idea is to use the brute force approach. We will find the divisors for every element in the ‘ARR’. If the count of divisors becomes greater than 4, we will move to the next element. And if after finding all the divisors of an element, the number of divisors is exactly 4 then we will sum the divisors.

 

Algorithm:

  • Declare an integer variable, ‘RESULT’ and initialize it with 0. The ‘RESULT’ will store the sum of divisors of all the integers in ‘ARR’ with exactly four divisors.
  • Run a loop for every ‘NUM’ in the ‘ARR’.
    • Declare two variables, ‘SUM’ and ‘COUNT’ and initialize them with 0. The ‘SUM’ will store the sum of divisors of ‘NUM’, and ‘COUNT’ will store the count of the divisors of the ‘NUM’.
    • Run a loop for i = 1 to ‘NUM’.
      • If ‘NUM % i == 0’, that shows that ‘i’ is a divisor of ‘NUM’. So,
        • Add ‘i’ to the ‘SUM’.
        • Increment the ‘COUNT’ by 1.
        • If ‘COUNT > 4’, that shows that ‘NUM’ has more than 4 divisors. So,
          • Break the loop and move to the next element in ‘ARR’.
    • If ‘COUNT == 4’, that shows that ‘NUM’ has exactly 4 divisors. So,
      • Add ‘SUM’ to the ‘RESULT’.
  • In the end, return ‘RESULT’.
Time Complexity

O(N * M), where ‘N’ is the number of integers in the array, ‘ARR’ and ‘M’ is the maximum value of the integer in the array, ‘ARR’.

 

The outer loop runs for every element of the array hence takes O(N) time. The inner loop runs till the value of every element and hence will take O(M) time in the worst case. Therefore, overall time complexity = O(N) * O(M) = O(N * M).

Space Complexity

O(1).

 

Since no auxiliary space is required. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Four Divisors
Full screen
Console