Print Characters At Prime Indices

Easy
0/40
Average time to solve is 15m
profile
Contributed by
3 upvotes
Asked in companies
IBMRazorpayTCS

Problem statement

You are given a string 'STR' of length 'N'. You need to return a string that will contain all the characters present at the prime indices of the original string. The relative order of characters in the new string should be exactly the same as it was in the original string.

Note:

1. Prime indices are those indices that are prime numbers i.e. all the numbers except 0 and 1 which are divisible by 1 and the number itself. For eg. If a character is at index 5 in some string, then it is at a prime index, as 5 is a prime number.

2. The given string may consist of characters ‘a’-’z’, ‘A’-’Z’, ‘0’-’9’ at any place.

3. The given string follows 0-based indexing. So, assume that the first character of the given string is at index 0.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer 'T' denoting the number of test cases.

The first and the only line of each test case contains the string 'STR'.
Output Format: 
The only line of output of each test case should contain the string consisting of characters at prime indices in the given string.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 50
1 <= N <= 10^4

Time Limit: 1 sec
Sample Input 1:
2
CodingNinjasIsTheBest
AmazonGoogleMicrosoftNetflix
Sample Output 1:
digissBs
aznoeisft
Explanation For Sample Input 1:

explanation_input1 explanation_input2

All the characters highlighted by arrows are at prime indices.
Sample Input 2:
2
CodingNinjas
CompetitiveProgramming
Sample Output 2:
digis
mpttPomi
Hint

Can you check whether current number is prime or not? 

Approaches (2)
Brute force.
  1. One of the most obvious solutions is to check each index individually for its primality and if it is prime then add the character at that index to the answer string.
  2. A prime number is a number that is divisible by 1 and the number itself.
  3. 1 is not a prime number.
  4. Iterate through the indices from 0 to ‘N’-1.
  5. For each of the indices greater than 1  in the given str up to ‘N'-1, where ‘N’ equals the length of the given ‘STR’.
  6. Let ‘CURRENTINDEX’ represent the current index.
  7. Check if any number from 2 to ‘CURRENTINDEX’ - 1 divides the ‘CURRENTINDEX’ or not.
  8. If any index divides ‘CURRENTINDEX’, then the current index i is not prime. Otherwise, it is prime and simply append that character to the answer string.
Time Complexity

O(N^2), where N is the size of the given string.

As we are using two for loops which run from 0 to N - 1. runtime complexity will be O(N^2).

Space Complexity

O(1), as we are using constant extra memory.

Code Solution
(100% EXP penalty)
Print Characters At Prime Indices
Full screen
Console