Find the count of M character words which have at least one character repeated
source link: https://www.geeksforgeeks.org/find-the-count-of-m-character-words-which-have-at-least-one-character-repeated/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
- Difficulty Level : Hard
- Last Updated : 01 Aug, 2019
Given two integers N and M, the task is count the total words of M character length formed by the given N distinct characters such that the words have at least one character repeated more than once.
Examples:
Input: N = 3, M = 2
Output: 3
Suppose the characters are {‘a’, ‘b’, ‘c’}
All 2 length words that can be formed with these characters
are “aa”, “ab”, “ac”, “ba”, “bb”, “bc”, “ca”, “cb” and “cc”.
Out of these words only “aa”, “bb” and “cc” have
at least one character repeated more than once.Input: N = 10, M = 5
Output: 69760
Approach:
Total number of M character words possible from N characters, total = NM.
Total number of M character words possible from N characters where no character repeats itself, noRepeat = NPM.
So, total words where at least a single character appear more than once is total – noRepeat i.e. NM – NPM.
Below is the implementation of the above approach:
- Python3
filter_none
edit
close
play_arrow
link
brightness_4
code
// C++ implementation for the above approach #include <math.h> #include <iostream> using namespace std; // Function to return the // factorial of a number int fact(int n) { if (n <= 1) return 1; return n * fact(n - 1); } // Function to return the value of nPr int nPr(int n, int r) { return fact(n) / fact(n - r); } // Function to return the total number of // M length words which have at least a // single character repeated more than once int countWords(int N, int M) { return pow(N, M) - nPr(N, M); } // Driver code int main() { int N = 10, M = 5; cout << (countWords(N, M)); return 0; } // This code is contributed by jit_t 69760
Attention reader! Don’t stop learning now. Get hold of all the important Java Foundation and Collections concepts with the Fundamentals of Java and Java Collections Course at a student-friendly price and become industry ready.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK