Last Updated: 11 Mar, 2021
LOOTCASE
Moderate
Asked in company
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.
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
Approaches
- 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.
- For optimizing the time complexity we use the concept of ‘Sieve of Eratosthenes’ for finding the prime numbers.
- Sieve of Eratosthenes is an optimized approach for finding prime numbers:
for (int p = 2; p * p < n; p++) {
if (prime[p] == false) // if number is not prime it is marked as false
for (int i = p * 2; i < n; i += p)
prime[i] = true; // if number is prime it is marked as true
}
- According to this approach, we mark all the numbers which are divisible by ‘2’’and are greater than or equal to the square of it in a bool array.
- Now starting from ‘2’ we go to every unmarked number and filled our bool array.
- So now all unmarked number is our prime numbers for these prime numbers now we declared an array which is used to store the count of digits of these prime numbers.
- So now we simply find out the digit with maximum frequency from this array and that digit is our required number. In case of a tie, we return the largest digit from them.