Posted: 11 Mar, 2021
Difficulty: Moderate


Try Problem

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


‘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’.
Both 'L' and 'R' are exclusive.

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’.
You are not required to print anything explicitly. It has already been taken care of. Just implement the function. 


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

Time Limit: 1 second    
Approach 1
  • 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.
Try Problem