Last Updated: 12 Dec, 2020

Three Factors

Moderate

Asked in companies

Solve now

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

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

In this approach, we will make a sieve array that maintains whether that particular index is a prime number or not. If the index is a prime number, then the sieve[index] is equal to 1. Otherwise, sieve[index] is equal to 0.

Now, after this, we have to traverse the input array ARR

if ARR[ind] is 1, then set result[ind] to 0 and move to the next element.
We will check if ARR[ind] is a perfect square and its square root is a prime, then set result[ind] as 1. Otherwise, set result[ind] as 0.

Algorithm:

Create a function hasThreeFactors(ARR,N). This function will return an array result that contains values 0 or 1.
- Create a result array of size N.
- Set the variable length as the minimum of the value 1000001 and Max(ARR).
- Create a sieve array of size length and initialize all elements with 0.
- Set ind as 2.
- We will iterate till the square of ind is less or equal to length.
  - We will check If sieve[ind] is equal to 0.
    - Set ind1 as 2 * ind.
    - We will iterate till ind1 is less than or equal to length. We will set sieve[ind1] as 1 and increment ind1 by ind.
- Iterate ind from 0 to N-1:
  - If ARR[ind] is equal to 1 then set result[ind] as 0 and move to the next element.
  - If ARR[ind] is a perfect square and sieve[sqrt(ARR[ind])] is 0 then set result[ind] as 1. Otherwise set result[ind] as 0.
- Return the result array.

Solve now