Last Updated: 6 Jul, 2022
K-Replacement
Easy
Asked in company
Bob is a student and learned about alphabets and prime numbers today. He still sometimes gets confused between normal numbers and prime numbers. So his teacher thought of giving him a fun game that can help him to get confident in this topic.
The game was, there is string ‘STR’ of length ‘N’ which includes alphabets and digits. There is also a special character ‘K’. The game was to replace every prime number that occurred in the string ‘STR’ with ‘K’.
Bob has solved the task and finished the game, but he still has doubt that the final string he got after the replacement is correct. So being his friend he asked you to help him with it.
So your task is to play the same game and return the correct final string after replacement.
NOTE: 1 is neither prime nor composite.
EXAMPLE :
Input: ‘N’ = 8, 'K' = ?, ‘STR’ = A12a3CbB
Output: A1?a?CbB
In this case, the numbers are ‘1’, ‘2’, and ‘3’ at ‘2nd’, ‘3rd’, and ‘5th’ positions respectively (1-based indexing). But only ‘2’ and ‘3’ are prime numbers, So after replacing them with ‘K’ the final string will be “A1?a?CbB”.
Input Format :
The first line will contain the integer ‘T’, the number of test cases.
Each test case consists of two lines.
The first line of input contains one integer and one character, ‘N’ and ‘K’ separated by spaces.
Followed by a line containing the string ‘STR’ of length ‘N’.
Output format :
For each test case, print the correct final string after replacement.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5
‘K’ is a lower-case or upper-case English letter or any special character like ‘#’, ‘?’, ‘%’, ‘@’, ‘(’ and ‘)’.
‘STR’ consists of lower-case or uppercase letters or digits.
It is guaranteed that sum of ‘N’ over all test cases is <= 10^5
Time Limit: 1 sec
Approaches
The idea for this approach is to first find or hard-code all the prime numbers from ‘0’ to ‘9’ and then iterate on the given string and if found any prime numbers, replace them with the given character ‘K’.
We can store all the prime numbers into a hash-set for O(1) access.
Algorithm:
// The function will return true if the given character is a number.
Int isDigit(X)
- If X lies in the range ‘0’ to ‘9’.
- Return the value of ‘X’ in the decimal system.
- Return ‘-1’.
// The function will return the correct final string after replacement
String kReplacement(N, K, STR)
- Create a hash-set ‘PRIMES’ and insert ‘2’, ‘3’, ‘5’, and ‘7’ into the map.
- Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Initialize a variable named ‘DIGIT’ with the value of ‘isDigit(STR[i])’.
- If ‘DIGIT != -1’ and ‘DIGIT’ is present in ‘PRIMES’.
- Assign ‘STR[i]’ value of ‘K’.
- Return ‘STR’.