Print characters at prime indices — Asked in Accenture Interview

2 min readJun 21, 2021

Problem Statement :

You are given a string ‘str’, you need to return a string which 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.

Sample Input:

AmazonGoogleMicrosoftNetflix

Sample Output:

aznoeisft

Approach :

Sieve of Eratosthenes.

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.

Time Complexity : O(Nlog(log N))
Space Complexity : O(N)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.