Last Updated: 23 Nov, 2020
Print Characters At Prime Indices
Easy
Asked in companies
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.
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
Approaches
- 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.
- A prime number is a number that is divisible by 1 and the number itself.
- 1 is not a prime number.
- Iterate through the indices from 0 to ‘N’-1.
- 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’.
- Let ‘CURRENTINDEX’ represent the current index.
- Check if any number from 2 to ‘CURRENTINDEX’ - 1 divides the ‘CURRENTINDEX’ or not.
- 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.
- Let's first understand the sieve of Eratosthenes to find primes efficiently.
- Since 2 is the smallest prime number, if string ‘STR’ length < 2, then return an empty string as the answer.
- In the sieve of Eratosthenes, we create a list of prime numbers from 2 to ‘N’, where ‘N’ is the length of the string.
- Initialize all list elements as prime, as initially, we assume that all numbers from 2 to ‘N’ are prime
- Start with PRIME = 2, If a PRIME is marked to true, mark all its multiples as non-primes, i.e. from >= 2 * PRIME, till the end of the list.
- Non-primes will be {2 * PRIME, 3 * PRIME, … PRIME*PRIME, PRIME*(PRIME+1), PRIME*(PRIME+2), PRIME(PRIME+3), ...} till index ‘N’ - 1 because all such indices have a common factor: prime so that all such numbers will be divisible by prime as well.
- After calculating primes in the list, iterate through the list from 2 to ‘N’-1. If the current index is marked as PRIME, append the character at this index to the answer string solution.