Given a string , the task is to check if the frequencies of all the characters of the string are prime or not. If all the frequencies are prime then print otherwise print .
Examples:
Input: str = “neveropen”
Output: No
Character Frequency g 2 e 4 k 2 s 2 f 1 o 1 r 1 It is clear that only the frequencies of g, k and s are prime.
Input: str = “aabbbccccc”
Output: Yes
Approach: Find the frequencies of all the characters present in the string and store them in a map. Then check whether all the frequencies are prime or not, if all the frequency are prime then print else .
Below is the implementation of the above approach:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // function that returns true // if n is prime else false bool isPrime( int n) { int i; // 1 is not prime if (n == 1) return false ; // check if there is any factor or not for (i = 2; i <= sqrt (n); i++) if (n % i == 0) return false ; return true ; } // function that returns true if // the frequencies of all the // characters of s are prime bool check_frequency(string s) { // create a map to store // the frequencies of characters map< char , int > m; for ( int i = 0; i < s.length(); i++) // update the frequency m[s[i]]++; // check whether all the frequencies // are prime or not for ( char ch = 'a' ; ch <= 'z' ; ch++) if (m[ch] > 0 && !isPrime(m[ch])) return false ; return true ; } // Driver code int main() { string s = "neveropen" ; // if all the frequencies are prime if (check_frequency(s)) cout << "Yes" << endl; else cout << "No" << endl; return 0; } |
Java
import java.util.*; // Java implementation of above approach class GFG { // function that returns true // if n is prime else false static boolean isPrime( int n) { int i; // 1 is not prime if (n == 1 ) { return false ; } // check if there is any factor or not for (i = 2 ; i <= Math.sqrt(n); i++) { if (n % i == 0 ) { return false ; } } return true ; } // function that returns true if // the frequencies of all the // characters of s are prime static boolean check_frequency( char [] s) { // create a map to store // the frequencies of characters HashMap<Character, Integer> m = new HashMap<Character, Integer>(); for ( int i = 0 ; i < s.length; i++) // update the frequency { if (m.containsKey(s[i])) { m.put(s[i], m.get(s[i]) + 1 ); } else { m.put(s[i], 1 ); } } // check whether all the frequencies // are prime or not for ( char ch = 'a' ; ch <= 'z' ; ch++) { if (m.get(ch) != null && m.get(ch) > 0 && !isPrime(m.get(ch))) { return false ; } } return true ; } // Driver code public static void main(String[] args) { String s = "neveropen" ; // if all the frequencies are prime if (check_frequency(s.toCharArray())) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } // This code contributed by Rajput-Ji |
Python3
# Python3 implementation of above approach import math as mt # function that returns true # if n is prime else false def isPrime(n): i = 2 # 1 is not prime if (n = = 1 ): return False # check if there is any factor or not for i in range ( 2 , mt.ceil(mt.sqrt(n))): if (n % i = = 0 ): return False return True # function that returns true if the # frequencies of all the characters # of s are prime def check_frequency(s): # create a map to store # the frequencies of characters m = dict () for i in range ( len (s)): # update the frequency if s[i] in m.keys(): m[s[i]] + = 1 else : m[s[i]] = 1 # check whether all the frequencies # are prime or not for ch in m: if m[ch] > 0 and isPrime(m[ch]) = = False : return False return True # Driver code s = "neveropen" # if all the frequencies are prime if (check_frequency(s)): print ( "Yes" ) else : print ( "No" ) # This code is contributed # by Mohit kumar 29 |
C#
// C# implementation of above approach using System; using System.Collections.Generic; class GFG { // function that returns true // if n is prime else false static bool isPrime( int n) { int i; // 1 is not prime if (n == 1) { return false ; } // check if there is any factor or not for (i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) { return false ; } } return true ; } // function that returns true if // the frequencies of all the // characters of s are prime static bool check_frequency( char [] s) { // create a map to store // the frequencies of characters Dictionary< char , int > m = new Dictionary< char , int >(); for ( int i = 0; i < s.Length; i++) // update the frequency { if (m.ContainsKey(s[i])) { var c = m[s[i]]+1; m.Remove(s[i]); m.Add(s[i], c); } else { m.Add(s[i], 1); } } // check whether all the frequencies // are prime or not for ( char ch = 'a' ; ch <= 'z' ; ch++) { if (m.ContainsKey(ch) && m[ch] > 0 && !isPrime(m[ch])) { return false ; } } return true ; } // Driver code public static void Main(String[] args) { String s = "neveropen" ; // if all the frequencies are prime if (check_frequency(s.ToCharArray())) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript implementation of above approach // function that returns true // if n is prime else false function isPrime(n) { var i; // 1 is not prime if (n == 1) return false ; // check if there is any factor or not for (i = 2; i <= Math.sqrt(n); i++) if (n % i == 0) return false ; return true ; } // function that returns true if // the frequencies of all the // characters of s are prime function check_frequency(s) { // create a map to store // the frequencies of characters var m = new Map(); for ( var i = 0; i < s.length; i++) // update the frequency if (m.has(s[i])) { m.set(s[i],m.get(s[i])+1); } else { m.set(s[i],1); } // check whether all the frequencies // are prime or not for ( var ch = 'a' .charCodeAt(0); ch <= 'z' .charCodeAt(0); ch++) if (m.get(String.fromCharCode(ch)) > 0 && !isPrime(m.get(String.fromCharCode(ch)))) return false ; return true ; } // Driver code var s = "neveropen" ; // if all the frequencies are prime if (check_frequency(s)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed byrutvik_56. </script> |
No
Complexity Analysis:
- Time Complexity: O((len(str))1/2)
- Auxiliary Space: O(len(str))
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!