Given a string of lowercase English alphabets. The task is to check if the count of distinct characters in the string is prime or not.
Examples:
Input : str = "neveropen" Output :Yes Explanation: The number of distinct characters in the string is 7, and 7 is a prime number. Input : str ="neveropen" Output : No
In this problem first we have to count the distinct characters in the string. We will use a map to store the frequency of each alphabets. The next step is to count the number of distinct characters, and check whether the number is prime or not .
If the number is prime we will print Yes, else No.
Below is the implementation of the above approach:
C++
// C++ program to check whether count of// distinct characters in a string// is Prime or not#include <bits/stdc++.h>using namespace std;// Find whether a number is prime or notbool 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;}// Count the distinct characters in a stringint countDistinct(string s){ // create a map to store the // frequency of characters unordered_map<char, int> m; // traverse the string for (int i = 0; i < s.length(); i++) { // increase the frequency of character m[s[i]]++; } return m.size();}// Driver codeint main(){ string str = "neveropen"; if (isPrime(countDistinct(str))) cout << "Yes" << endl; else cout << "No" << endl; return 0;} |
Java
// Java program to check whether count of// distinct characters in a string// is Prime or notimport java.util.*;class GFG{ // Find whether a number is prime or not 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; } // Count the distinct characters in a string static int countDistinct(String s) { // create a map to store the // frequency of characters Set<Character> m = new HashSet<Character>(); // traverse the string for (int i = 0; i < s.length(); i++) { // increase the frequency of character m.add(s.charAt(i)); } return m.size(); } // Driver code public static void main(String []args) { String str = "neveropen"; if (isPrime(countDistinct(str))) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by ihritik |
Python3
# Python 3 program to check whether# count of distinct characters in a # string is Prime or not# from math library import # sqrt methodfrom math import sqrt# Find whether a number # is prime or notdef isPrime(n) : # 1 is not prime if n == 1 : return False # check if there is any # factor or not for i in range(2, int(sqrt(n)) + 1) : if n % i == 0 : return False return True# Count the distinct characters # in a stringdef countDistinct(s) : # create a dictionary to store # the frequency of characters m = {} # dictionary with keys and its # initialize with value 0 m = m.fromkeys(s, 0) # traverse the string for i in range(len(s)) : # increase the frequency # of character m[s[i]] += 1 return len(m.keys())# Driver code if __name__ == "__main__" : str = "neveropen" if isPrime(countDistinct(str)) : print("Yes") else : print("No") # This code is contributed# by ANKITRAI1 |
C#
// C# program to check whether count of // distinct characters in a string // is Prime or not using System;using System.Collections.Generic;class GFG { // Find whether a number is prime or not 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; } // Count the distinct characters in a string static int countDistinct(String s) { // create a map to store the // frequency of characters HashSet<char> m = new HashSet<char>(); // traverse the string for (int i = 0; i < s.Length; i++) { // increase the frequency of character m.Add(s[i]); } return m.Count; } // Driver code public static void Main(String []args) { String str = "neveropen"; if (isPrime(countDistinct(str))) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } // This code has been contributed by 29AjayKumar |
Javascript
<script>// Javascript program to check whether count of// distinct characters in a string// is Prime or not// Find whether a number is prime or notfunction 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;}// Count the distinct characters in a stringfunction countDistinct(s){ // create a map to store the // frequency of characters var m = new Map(); // traverse the string for (var i = 0; i < s.length; i++) { // increase the frequency of character if(m.has(s[i])) { m.set(s[i], m[s[i]]+1); } else { m.set(s[i],1); } } return m.size;}// Driver codevar str = "neveropen";if (isPrime(countDistinct(str))) document.write( "Yes" );else document.write( "No" );// This code is contributed by rutvik_56.</script> |
Output
Yes
Complexity Analysis:
- Time Complexity: O((len(str))1/2)
- Auxiliary Space: O(len(str))
Method 2: Using Counter function:
- Count the frequencies of all elements using Counter function and number of keys of this frequency dictionary gives the count and check whether it is prime or not.
Below is the implementation:
C++
// Cpp program for the above approach#include <iostream>#include <unordered_map>#include <cmath>using namespace std;bool isPrime(int n) { if (n == 1) { // 1 is not prime return false; } // Check if there is any factor or not for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { return false; } } return true;}bool countDis(string str) { // Stores all frequencies unordered_map<char, int> freq; for (int i = 0; i < str.length(); i++) { char ch = str[i]; freq[ch]++; } // Return the size of the freq object if (isPrime(freq.size())) { return true; } else { return false; }}// Driver codeint main() { string S = "neveropen"; cout << countDis(S) << endl; return 0;}//This code is contributed by shivamsharma215//Output is 1 i.e. True |
Java
import java.util.*;public class Main { public static boolean isPrime(int n) { if (n == 1) { // 1 is not prime return false; } // Check if there is any factor or not for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } public static boolean countDis(String str) { // Stores all frequencies Map<Character, Integer> freq = new HashMap<>(); for (int i = 0; i < str.length(); i++) { char ch = str.charAt(i); freq.put(ch, freq.getOrDefault(ch, 0) + 1); } // Return the size of the freq object if (isPrime(freq.keySet().size())) { return true; } else { return false; } } // Driver code public static void main(String[] args) { String S = "neveropen"; System.out.println(countDis(S)); }} |
Python3
# Python program for the above approachfrom collections import Counterfrom math import sqrt as sqrtdef isPrime(n): # 1 is not prime if n == 1: return False # check if there is any # factor or not for i in range(2, int(sqrt(n)) + 1): if n % i == 0: return False return True# Function to count the number of distinct# characters present in the string# str and check whether it is primedef countDis(str): # Stores all frequencies freq = Counter(str) # Return the size of the freq dictionary if(isPrime(len(freq))): return True else: return False# Driver Codeif __name__ == "__main__": # Given string S S = "neveropen" print(countDis(S))# This code is contributed by vikkycirus |
C#
using System;using System.Collections.Generic;using System.Linq;public class Gfg{ public static bool isPrime(int n) { if (n == 1) // 1 is not prime { return false; } // Check if there is any factor or not for (int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } public static bool countDis(string str) { // Stores all frequencies Dictionary<char, int> freq = new Dictionary<char, int>(); foreach (char ch in str) { if (freq.ContainsKey(ch)) { freq[ch]++; } else { freq.Add(ch, 1); } } // Return the size of the freq object if (isPrime(freq.Count)) { return true; } else { return false; } } public static void Main() { string S = "neveropen"; Console.WriteLine(countDis(S)); }} |
Javascript
// Javacript program for the above approachfunction isPrime(n) { if (n === 1) { // 1 is not prime return false; } // Check if there is any factor or not for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i === 0) { return false; } } return true;}function countDis(str){ // Stores all frequencies let freq = {}; for (let i = 0; i < str.length; i++) { freq[str[i]] = (freq[str[i]] || 0) + 1; } // Return the size of the freq object if (isPrime(Object.keys(freq).length)) { return true; } else { return false; }}// Driver codelet S = "neveropen";console.log(countDis(S));// This code is contributed by codebraxnzt |
Output
True
- Time Complexity: O((len(str))1/2)
- Auxiliary Space: O(len(str))
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!
