Problem

Submissions

Hints & solutions

Discuss

LOOTCASE

Moderate

0/80

Average time to solve is 10m

Contributed by

5 upvotes

Asked in company

Problem statement

Ninja is living a simple life like a middle-class man. But one day he was coming back from the office. He saw a car tumbling down the road. He goes near the car and he saw a man deeply wounded. Ninja tries to pull out the man from the car but the man says he is dying and asks Ninja to find out the solution of the quiz which is written on paper which can lead to him an address where he has put the suitcase full of money.

So the quiz is two numbers were written on the paper let's assume ‘L’ and ‘R’. The house number where the suitcase has been hidden is that digit of prime number which can occur between ‘L’ and ‘R’ and has a maximum frequency.

Help our Ninja to find that digit so he is able to find out that suitcase full of money.

Your task is to find out the highest occurring digit in prime number which lies in between given numbers ‘L+1’ and ‘R-1’ as 'L' and 'R' are exclusive. If two numbers have the same frequency return the largest and if no prime number exists in that range return ‘-1’.

Example:

‘L = 1’ and  ‘R = 15’ so between these numbers prime numbers lie are - {2, 3, 5, 7, 11, 13}. As you can see ‘11’ has two ‘1s’ and ‘13’ has one ‘1’ so the frequency of ‘1’ is ‘3’ which is maximum hence our answer is ‘1’.

Note:

Both 'L' and 'R' are exclusive.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains a ‘T’ number of test cases.

The first line of each test case contains two space-separated integers ‘L’ and ‘R’ denoting the range.

Output Format:

For each test case, return the number with the highest frequency. In case more than one number has a maximum frequency, then return the number with the highest value. In case no prime number lies in between the given range return as ‘-1’.

Note:

You are not required to print anything explicitly. It has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= L <= R <= 10^3

Time Limit: 1 second

Sample Input 1:

2
1 10
21 31

Sample Output 1:

7
2

Explanation of Sample Input 1:

Test Case 1:

According to this test case given range is ‘1’ and ‘10’ so prime numbers between this range are {2, 3, 5, 7}. All numbers have the same frequency i.e. ‘1’ of ‘2’, ‘3’, ‘5’, ‘7’ but ‘7’ is the maximum element so our answer is ‘7’.

Test Case 2:

For this test case given range is ‘21’ and ‘31’. The prime numbers between this range are {23, 29}. ‘2’ is the digit that has maximum frequency i.e. ‘2’ so our answer is ‘2’ (other digits ‘3’ and ‘9’ have only ‘1’ frequency).

Sample Input 2 :

2
3 9
2 20

Sample Output 2 :

7
1

Hint 1

Hint 2

Can you count the digit separately?

Approaches (2)

Approach 1

Approach 2

Brute Approach

First, we find out the prime numbers by simply running a loop between our range ‘L’ and ‘R’ by checking the number is prime or not.
If the number is prime :
- Now for every prime number, we store the count of each digit by separating the digit from the number.
- We use an array ‘ARR[]’ for storing the count of the number like we have to only consider {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} these digits.
After checking for every number
Now we simply find out the digit from this ‘ARR[]’ which has the highest frequency in case of tie largest digit is our answer.
In the end, return the maximum frequency digit.

Time Complexity

O(R * max(log(R), R)), where ‘R’ is the highest number of the range.

We are iterating a loop from ‘L’ to ‘R’, the first check number is prime or not takes ‘R' time and if the number is prime then checking of every number takes log(R) time.

Space Complexity

O(1),

We are using constant space.

(100% EXP penalty)

LOOTCASE

Console