Prime Time Again

Moderate
0/80
Average time to solve is 25m
13 upvotes
Asked in companies
Inca Infotech Technologies Private LimitedPinnacle Works InfotechNCR Corporation

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
36 3
8 2
Sample Output 1:
2
1
Explanation of sample input 1:
Test Case 1:

36 hour day can divide in such three parts:

 1  2  3  4  5  6  7  8  9 10 11 12     -Part 1
13 14 15 16 17 18 19 20 21 22 23 24     -Part 2
25 26 27 28 29 30 31 32 33 34 35 36     -Part 3

1-13-25  Not a prime group because 1, 25 are not prime.
2-14-26  Not a prime group because 14, 25  are not prime.
3-15-27  Not a prime group because 15 is not prime.
4-16-28  Not a prime group because 4, 16, 28 are not prime.
5-17-29  Because 3, 17, 29 all are prime, it is an equivalent prime group.
6-18-30  Not a prime group because 6,18,30 are not prime.
7-19-31  Because 7, 19, 31 all are prime, it is an equivalent prime group.
8-20-32  Not a prime group, because 8, 20, 32 are not prime.
9-21-33  Not a prime group because 9, 21, 33 are not prime.
10-22-34 Not a prime group because 10, 22, 34 are not prime.
11-23-35  Not a prime group because 35 is not prime.
12-24-36 Not a prime group because 12, 24, 26 are not prime.

Hence there are 2 equivalent prime groups in the above format  which is 5-17-29 and 7-19-31


Test case 2:

8 hours a day can divide into 2 such parts (1-4) and (5-8)
Hence only one combination of 3-7 is a prime group because 3 and 7 both are prime and are equivalent hours.
Sample Input 2:
2
24 2
49 7
Sample Output 2:
3
0
Hint

Try comparing each equivalent group of hours for prime groups. 

Approaches (3)
Brute Force
  • 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’
Time Complexity

O(D^2), Where ‘D’ is the number of hours in a day.

 

In this approach, we are iterate rows from 0 to P-1 and for every row, we iterate col from 0 to D/P-1 and for every number, at ARR[ROW][COL] we are checking is prime or not.

 

Total time complexity is P*(D/P)*D = D^2, Where an order of  ‘D’ time is required to check number is prime or not

Space Complexity

O(D), Where ‘D’ is the number of hours in a day.

 

Space required to create an array of size  P rows and (D/P) columns.

Code Solution
(100% EXP penalty)
Prime Time Again
Full screen
Console