Last Updated: 15 Apr, 2021

Four Divisors

Moderate

Asked in company

Solve now

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.

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.

Solve now

Approaches

01 Approach

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’.

Solve now

02 Approach

For any integer greater than 1, ‘NUM’, it is obvious that 1 and ‘NUM’ are the divisors of ‘NUM’. So we already have two divisors. Also, if ‘i’ is a divisor of ‘NUM’ then ‘NUM / i’ is also a divisor of ‘NUM’. It means we only have to find a divisor, ‘i’ in between 2 to SQRT(NUM), and thus we will have 1, ‘NUM’, ‘i’ and ‘NUM / i’ as four divisors.

Please note that if ‘NUM’ is a perfect square and ‘i’ is a divisor of ‘NUM’ then ‘i’ and ‘NUM / i’ will be the same integer. In that case, ‘NUM’ will have only three 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’. Initialize ‘SUM’ by ‘1 + NUM’ and ‘COUNT’ by 2. 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 = 2 to SQRT(NUM).
  - If ‘NUM % i == 0’, that shows that ‘i’ is a divisor of ‘NUM’. So, check
    - If ‘i == NUM / i’ that shows that ‘i’ and ‘NUM / i’ are the same divisor of ‘NUM’. Therefore,
      - Add ‘i’ to the ‘SUM’.
      - Increment the ‘COUNT’ by 1.
    - Else
      - Add ‘i’ and ‘NUM / i’ to the ‘SUM’.
      - Increment the ‘COUNT’ by 2.
    - 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’.

Solve now