Three Factors

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
6 upvotes
Asked in companies
CognizantAdobeCiti Bank

Problem statement

You are given an array ‘ARR’ consisting of ‘N’ positive integers. Your task is to find if the number has exactly 3 factors for each number in the array ‘ARR’.

You have to return an array consisting of ‘0,’ and ‘1’ where ‘0’ means that ‘ARR[index]’ does not have 3 factors and ‘1’ means ‘ARR[index]’ has exactly 3 factors.

For Example: 
If ‘N’ = 4 and ‘ARR’ = [3, 5, 4, 2]. 
3 has 2 factors, which are 1 and 3.
5 has 2 factors, which are 1 and 5.
4 has 3 factors, which are  1, 2 and 4.
2 has 2 factors, which are 1 and 2.
Hence, the answer is [0, 0, 1, 0].
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
 The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array.

The next line contains ‘N’ space-separated integers denoting the elements of array ‘ARR’.
Output format : 
For each test case, print an array containing 0 and 1 where 1 is present if the number ‘ARR[index]’ has exactly 3 factors. Otherwise, 0 is present.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
 1 <= T <= 10
 1 <= N <= 10^6
 1 < ARR[index] <= 10^12

Time Limit: 1 second
Sample Input 1 :
2
3
4  5  6
4
8 9 7 13
Sample Output 1 :
1 0 0
0 1 0 0
Explanation:
In test case 1: There are 3 elements in the input array.
4 has 3 factors, which are 1, 2, and 4.
5 has 2 factors which are 1 and 5.
6 has 4 factors which are 1, 2, 3, and 6.
So the answer is [1, 0, 0].

In test case 2: There are 4 elements in the input array. 
8 has 4 factors, which are 1, 2, 4, and 8
9 has 3 factors, which are 1, 3,and 9
7 has 2 factors, which are 1,and 7
13 has 2 factors, which are 1,and 13 
So the answer is [0, 1, 0, 0].
Sample Input 2:
1
5
13 19 21 23 25
Sample Output 2:
0 0 0 0 1
Hint

Try to think of a brute force approach.

Approaches (2)
Brute Force

In this approach, we will implement a function in which we have to pass an integer, and for each integer passed, the function returns the number of factors of that number. So we iterate over the input array ARR, and we pass each ARR[index] to this function. If it returns 3, the result[index] is set to 1. Otherwise, it is set to 0. In the end, we will return the array result. 

 

Algorithm:

  • Make a function countFactors(num). This function returns the number of factors corresponding to the num.
  • Initialize a variable numOfFactors with 0.
  • Iterate ind from 1 to num: 
    • If num is divisible by ind then increment numOfFactors with 1.
  • Return numOfFactors, which is the total number of factors of num.
  • Make a function named hasThreeFactors(ARR,N). This function will return an array result that contains values 0 or 1.
    • Create a result array of size N.
    • Iterate ind from 0 to N - 1:  
      • If countFactors(ARR[ind]) is equal to 3 then set result[ind] as 1. Otherwise set result[ind] as 0.
    • Return the result array.
Time Complexity

O(N * Max(ARR)) where N is the number of elements in the input array.


For each element of the array ARR, we have to traverse from 1 to that element value. Hence, the overall time complexity is O(N * Max(ARR)). 

Space Complexity

O(N) where N is the number of elements in the input array.

 

The space complexity O(N) is used to make the result array. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Three Factors
Full screen
Console