Last Updated: 5 Nov, 2020
Prime Time Again
Moderate
Asked in companies
You have been given two integers ‘DAY_HOURS’ and ‘PARTS’. Where ‘DAY_HOURS’ is the number of hours in a day and a day can be divided into ‘PARTS’ equal parts. Your task is to find total instances of equivalent prime groups. Prime group refers to the group of elements (hours) which are prime and measure the same equivalent time since the start of the day.
For example, if we consider ‘DAY_HOURS’ to be 24 and ‘PARTS’ to be 2, then the day of total 24 hours is divided into 2 parts ( 1 - 12 ) and ( 13 - 24 ). 5 hours in the first part of the day is equivalent to 17, which is 5 hours into the second part of the day. And since 5 and 17 both are prime, they can be considered as a prime group.
Note:
1. Day starts with hour 1 and ends with hour ‘DAY_HOURS’.
2. Each hour of the prime group should be in a different part of the day.
3. If there is no prime group then return zero.
4. ‘DAY_HOURS’ should be divisible by ‘PARTS’, meaning that the number of hours per part (DAY_HOURS/PARTS) should be a natural number.
Example:
Let ‘DAY_HOURS’ = 20 and ‘PARTS’ = 2
Hence the view of our day would be in the following format:
1 2 3 4 5 6 7 8 9 10 - Part 1
11 12 13 14 15 16 17 18 19 20 - Part 2
1-11 Not a prime group because 1 is not prime.
2-12 Not a prime group because 12 is not prime.
3-13 Because both 3 and 13 are prime, it is an equivalent prime group.
4-14 Not a prime group because 4 and 14 are not prime.
5-15 Not a prime group because 15 is not prime.
6-16 Not a prime group, because 6 and 16 are not prime.
7-17 Because both 7 and 17 are prime, it is an equivalent prime group.
8-18 Not a prime group, because 8 and 18 are, is not prime.
9-19 Not a prime group because 9 is not prime.
10-20 Not a prime group because both 10 and 20 are not prime.
Hence there are 2 equivalent prime groups in the above format which are 3-13 and 7-17.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first and the only line of each test case contains two space-separated integers ‘DAY_HOURS’ and ‘PARTS’.
Output Format
The output for each test case contains a single integer denoting the number of instances of equivalent prime groups.
The output of each test case will be printed in a separate line.
Note
You are not required to print the output, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 100
10 <= DAY_HOURS <= 5 * 10^3
2 <= PARTS <= 10^3
Time Limit: 1 second
Approaches
- This is a Naive/Brute Force approach
- Create a 2-d array of size ‘P’ rows and ‘D/P’ columns and assign 1 to ‘D’ value in each cell.
- Take an example with ‘D’ being 12 and ‘P’ being 2, then create an array [ [1,2,3,4,5,6] [7,8,9,10,11,12] ]
- Keep track of the number of prime group instances using a ‘PRIME_GROUP’ variable, which would be initialized to 0.
- We can easily observe that each column in the array represents the same equivalent group of hours.
- Do column level traversal, which means we will be traversing through all the equivalent hours and check if all elements of the column prime or not .
- If equivalent group is prime group then increase the count of ‘PRIME_GROUP’
- This is the space optimization method of Approach 1
- Each hour which we used to store in ARR[ROW][COL] in the previous method can be calculated by the equation ‘ROW*(D/P)+col+1’.
- Suppose ‘D’ is 20 and ‘P’ is 2, hence the division would be as follows: [ [1,2,3,4,5,6,7,8,9,10],[11,12,13,14,15,16,17,19,20] ] ARR[0][0]=1 for this, row number is 0 and col number is 0, can find with ‘ROW*(D/P)+COL+1’ = 0*(20/2)+0+1 = 1 and ARR[1][2]=13 for this ROW number is 1 and COL number is 2 , can find with ‘ROW*(D/P)+COL+1’ = 1* (20/2)+2+1= 13
- Hence we can iterate the col from 0 to D/P -1 because there is a total D/P number of hours in a single part of the day.
- For each row, we can do column level traversal and iterate from 0 to P-1 which would contain a group of all equivalent hours in the Day. While doing column level traversal and check if all elements of the column are prime or not
- In each iteration keep track of the count of total equivalent prime groups
- This is the optimization of Approach 2
- Create a list of size 5001 and assign all values True
- Call it ‘PRIME_ARR’ to keep track of number ‘i’ is prime or not
- Initially, Let ‘K’ equals 2, which is the first prime number.
- Iterate from ‘K’^2 to 5001
- If ‘PRIME_ARR[K]’ is True then all the multiples of of ‘K’ will be non-prime
- Hence assign all multiples of ‘K’ to non-prime with ‘PRIME_ARR[X]’=False, Where ‘X’ is multiple of ‘K’.
- Then increase the value of ‘K’ by 1 and repeat step 5
- Hence, in each test case, while iterating through the hours, no need to find whether the number/hour is prime or not.