Given a string str of lowercase English alphabets, the task is to check whether the string is a vowel prime or not. A string is said to be vowel prime if all the vowels in the string appear at only prime indices.
Examples:
Input: str = “neveropen”
Output: No
str[1] = ‘e’ is a vowel but 1 is not prime.
Input: str = “bcae”
Output: Yes
All the vowels are at prime indices i.e. 2 and 3.
Approach: Use Sieve of Eratosthenes to find all the prime numbers less than N so that every index of the string can be checked for primality. Now, if there is some non-prime index such that the character at that position is a vowel then the string is not vowel prime else it is.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if c is a vowelbool isVowel(char c){ if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false;}// Function that returns true if all the vowels in// the given string are only at prime indicesbool isVowelPrime(string str, int n){ // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. bool prime[n]; memset(prime, true, sizeof(prime)); // 0 and 1 are not prime prime[0] = false; prime[1] = false; for (int p = 2; p * p < n; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for (int i = p * p; i < n; i += p) prime[i] = false; } } // For every character of the given string for (int i = 0; i < n; i++) { // If current character is vowel // and the index is not prime if (isVowel(str[i]) && !prime[i]) return false; } return true;}// Driver codeint main(){ string str = "neveropen"; int n = str.length(); if (isVowelPrime(str, n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Function that returns true // if c is a vowelstatic boolean isVowel(char c){ if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false;}// Function that returns true if all the vowels in// the given string are only at prime indicesstatic boolean isVowelPrime(String str, int n){ // Create a boolean array "prime[0..n]" and // initialize all entries it as true. // A value in prime[i] will finally be false // if i is Not a prime, else true. boolean []prime = new boolean[n]; Arrays.fill(prime, true); // 0 and 1 are not prime prime[0] = false; prime[1] = false; for (int p = 2; p * p < n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for (int i = p * p; i < n; i += p) prime[i] = false; } } // For every character of the given string for (int i = 0; i < n; i++) { // If current character is vowel // and the index is not prime if (isVowel(str.charAt(i)) && !prime[i]) return false; } return true;}// Driver codepublic static void main(String[] args){ String str = "neveropen"; int n = str.length(); if (isVowelPrime(str, n)) System.out.println("Yes"); else System.out.println("No");}}// This code is contributed by Princi Singh |
Python3
# Python3 implementation of the approach# Function that returns true if c is a voweldef isVowel(c): if (c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'): return True return False# Function that returns true if # all the vowels in the given string # are only at prime indicesdef isVowelPrime(Str, n): # Create a boolean array "prime[0..n]" # and initialize all entries in it as true. # A value in prime[i] will finally be false # if i is Not a prime, else true. prime = [True for i in range(n)] # 0 and 1 are not prime prime[0] = False prime[1] = False for p in range(2, n): if p * p > n: break # If prime[p] is not changed, # then it is a prime if (prime[p] == True): # Update all multiples of p greater than or # equal to the square of it # numbers which are multiple of p and are # less than p^2 are already been marked. for i in range(2 * p, n, p): prime[i] = False # For every character of the given String for i in range(n): # If current character is vowel # and the index is not prime if (isVowel(Str[i]) and prime[i] == False): return False return True# Driver codeStr= "neveropen";n = len(Str)if (isVowelPrime(Str, n)): print("Yes")else: print("No")# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System; class GFG{// Function that returns true // if c is a vowelstatic Boolean isVowel(char c){ if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false;}// Function that returns true if all the vowels in// the given string are only at prime indicesstatic Boolean isVowelPrime(String str, int n){ // Create a boolean array "prime[0..n]" and // initialize all entries it as true. // A value in prime[i] will finally be false // if i is Not a prime, else true. Boolean []prime = new Boolean[n]; for(int i = 0; i < n; i++) prime[i] = true; // 0 and 1 are not prime prime[0] = false; prime[1] = false; for (int p = 2; p * p < n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p greater than // or equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for (int i = p * p; i < n; i += p) prime[i] = false; } } // For every character of the given string for (int i = 0; i < n; i++) { // If current character is vowel // and the index is not prime if (isVowel(str[i]) && !prime[i]) return false; } return true;}// Driver codepublic static void Main(String[] args){ String str = "neveropen"; int n = str.Length; if (isVowelPrime(str, n)) Console.WriteLine("Yes"); else Console.WriteLine("No");}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation of the approach// Function that returns true if c is a vowelfunction isVowel(c){ if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false;}// Function that returns true if all the vowels in// the given string are only at prime indicesfunction isVowelPrime(str, n){ // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. var prime = Array(n).fill(true); // 0 and 1 are not prime prime[0] = false; prime[1] = false; for (var p = 2; p * p < n; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for (var i = p * p; i < n; i += p) prime[i] = false; } } // For every character of the given string for (var i = 0; i < n; i++) { // If current character is vowel // and the index is not prime if (isVowel(str[i]) && !prime[i]) return false; } return true;}// Driver codevar str = "neveropen";var n = str.length;if (isVowelPrime(str, n)) document.write( "Yes");else document.write( "No");</script> |
Output:
No
Time Complexity: O(n* log(log n))
Auxiliary Space: O(n), where n is the length of the given string.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
