K-Replacement

Easy
0/40
Average time to solve is 5m
profile
Contributed by
3 upvotes
Asked in company
Zivost Technologies

Problem statement

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”.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3 ?
1a2
6 %
Ax1yB3
Sample Output 1 :
1a?
Ax1yB%
Explanation Of Sample Input 1 :
For the first test case, the numbers are at the ‘1st’ and ‘3rd’ positions. But only ‘2’ is prime. Hence the final string after the replacement is “1a?”.

Hence, the output will be: 1a?

For the second test case, the numbers are at the ‘3rd’ and ‘6th’ positions respectively.  But only ‘3’ is prime. Hence the final string after the replacement is “Ax1yB%”.

Hence, the output will be: Ax1yB%
Sample Input 2 :
2
7 #
AbcDFgx
10 (
0123456789
Sample Output 2 :
AbcDFgx
01((4(6(89
Hint

Can we store all the primes and use them in some way?.

Approaches (1)
String Manipulation

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

O(N), Where ‘N’ is the input integer.

We iterate on the given string ‘STR’ of length ‘N’ and replace all the prime numbers with ‘K’ in O(1), hence the time complexity will be O(N)

Space Complexity

O(1),

 

As we only used some temporary loop variables and a hash-set of size ‘4’, the space complexity will be O(1).

Code Solution
(100% EXP penalty)
K-Replacement
Full screen
Console