Given two positive integers N and M, the task is to calculate the number of non-palindromic strings of length M using given N distinct characters.
Note: Each distinct character can be used more than once.
Examples:
Input: N = 3, M = 2
Output: 6
Explanation:
Since only 3 characters are given, those 3 characters can be used to form 32 different strings. Out of these, only 3 strings are palindromic. Hence, the remaining 6 strings are palindromic.Input: N = 26, M = 5
Output: 11863800
Approach:
Follow the steps below to solve the problem:
- Total number of strings of length M using given N characters will be NM.
- For a string to be a palindrome, the first half and second half should be equal. For even values of M, we need to select only M/2 characters from the given N characters. For odd values, we need to select M/2 + 1 characters from the given N characters. Since repetitions are allowed, the total number of palindromic strings of length M will be N(M/2 + M%2).
- The required count of non-palindromic strings is given by the following equation:
NM - N(M/2 + M%2)
Below is the implementation of the above approach:
C++
// C++ Program to count// non-palindromic strings// of length M using N // distinct characters#include <bits/stdc++.h>using namespace std;// Iterative Function to calculate// base^pow in O(log y)unsigned long long power( unsigned long long base, unsigned long long pow){ unsigned long long res = 1; while (pow > 0) { if (pow & 1) res = (res * base); base = (base * base); pow >>= 1; } return res;}// Function to return the // count of non palindromic stringsunsigned long long countNonPalindromicString( unsigned long long n, unsigned long long m){ // Count of strings using n // characters with // repetitions allowed unsigned long long total = power(n, m); // Count of palindromic strings unsigned long long palindrome = power(n, m / 2 + m % 2); // Count of non-palindromic strings unsigned long long count = total - palindrome; return count;}int main(){ int n = 3, m = 5; cout<< countNonPalindromicString(n, m); return 0;} |
Java
// Java program to count non-palindromic// strings of length M using N distinct// characters import java.util.*;class GFG{// Iterative Function to calculate// base^pow in O(log y)static long power(long base, long pow){ long res = 1; while (pow > 0) { if ((pow & 1) == 1) res = (res * base); base = (base * base); pow >>= 1; } return res;}// Function to return the // count of non palindromic stringsstatic long countNonPalindromicString(long n, long m){ // Count of strings using n // characters with // repetitions allowed long total = power(n, m); // Count of palindromic strings long palindrome = power(n, m / 2 + m % 2); // Count of non-palindromic strings long count = total - palindrome; return count;} // Driver codepublic static void main(String[] args){ int n = 3, m = 5; System.out.println( countNonPalindromicString(n, m));}}// This code is contributed by offbeat |
Python3
# Python3 program to count non-palindromic strings# of length M using N distinct characters # Iterative Function to calculate# base^pow in O(log y)def power(base, pwr): res = 1 while(pwr > 0): if(pwr & 1): res = res * base base = base * base pwr >>= 1 return res# Function to return the count # of non palindromic stringsdef countNonPalindromicString(n, m): # Count of strings using n # characters with # repetitions allowed total = power(n, m) # Count of palindromic strings palindrome = power(n, m // 2 + m % 2) # Count of non-palindromic strings count = total - palindrome return count# Driver codeif __name__ == '__main__': n = 3 m = 5 print(countNonPalindromicString(n, m))# This code is contributed by Shivam Singh |
C#
// C# program to count non-palindromic// strings of length M using N distinct// characters using System;class GFG{// Iterative Function to calculate// base^pow in O(log y)static long power(long Base, long pow){ long res = 1; while (pow > 0) { if ((pow & 1) == 1) res = (res * Base); Base = (Base * Base); pow >>= 1; } return res;}// Function to return the // count of non palindromic stringsstatic long countNonPalindromicString(long n, long m){ // Count of strings using n // characters with // repetitions allowed long total = power(n, m); // Count of palindromic strings long palindrome = power(n, m / 2 + m % 2); // Count of non-palindromic strings long count = total - palindrome; return count;} // Driver codepublic static void Main(String[] args){ int n = 3, m = 5; Console.WriteLine( countNonPalindromicString(n, m));}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript program to count non-palindromic// strings of length M using N distinct// characters// Iterative Function to calculate// base^pow in O(log y)function power(base, pow){ let res = 1; while (pow > 0) { if ((pow & 1) == 1) res = (res * base); base = (base * base); pow >>= 1; } return res;}// Function to return the // count of non palindromic stringsfunction countNonPalindromicString(n, m){ // Count of strings using n // characters with // repetitions allowed let total = power(n, m); // Count of palindromic strings let palindrome = power(n, m / 2 + m % 2); // Count of non-palindromic strings let count = total - palindrome; return count;} // Driver Codelet n = 3, m = 5;document.write(countNonPalindromicString(n, m));// This code is contributed by sanjoy_62</script> |
Output
216
Time Complexity: O(log(M))
Auxiliary Space: O(1)
Efficient Approach:
- We need to count the number of non-palindromic strings of length M using N distinct characters
- The total number of strings of length M using N distinct characters is N^M.
- We need to subtract the number of palindromic strings of length M from the above result to get the count of non-palindromic strings.
- For a given length M, we can calculate the number of palindromic strings by counting the number of strings that can be formed using the first M/2 characters and then squaring the result.
- If M is odd, then we multiply the result by N as the middle character can be any of the N characters.
- Subtracting the number of palindromic strings from N^M will give us the required count of non-palindromic strings.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;long long countNonPalindromicStrings(int N, int M) { long long countPalindromicStrings = 0; // Count number of palindromic strings if (M % 2 == 0) { // If M is even countPalindromicStrings = pow(N, M/2); } else { // If M is odd countPalindromicStrings = pow(N, (M-1)/2) * N; } // Count number of non-palindromic strings return pow(N, M) - countPalindromicStrings;}int main() { int N = 3, M = 2; cout << countNonPalindromicStrings(N, M) << endl; // Print the result return 0;} |
Java
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = 3; // Replace with your desired N value int M = 2; // Replace with your desired M value long result = countNonPalindromicStrings(N, M); System.out.println(result); } public static long countNonPalindromicStrings(int N, int M) { long countPalindromicStrings = 0; // Count number of palindromic strings if (M % 2 == 0) { // If M is even countPalindromicStrings = (long) Math.pow(N, M / 2); } else { // If M is odd countPalindromicStrings = (long) (Math.pow(N, (M - 1) / 2) * N); } // Count number of non-palindromic strings return (long) Math.pow(N, M) - countPalindromicStrings; }} |
Python
def count_non_palindromic_strings(N, M): count_palindromic_strings = 0 # Count number of palindromic strings if M % 2 == 0: # If M is even count_palindromic_strings = N ** (M // 2) else: # If M is odd count_palindromic_strings = N ** ((M - 1) // 2) * N # Count number of non-palindromic strings return N ** M - count_palindromic_stringsdef main(): N, M = 3, 2 print(count_non_palindromic_strings(N, M))if __name__ == "__main__": main() |
C#
using System;class GFG { static long CountNonPalindromicStrings(int N, int M) { long countPalindromicStrings = 0; // Count number of palindromic strings if (M % 2 == 0) { // If M is even countPalindromicStrings = (long)Math.Pow(N, M / 2); } else { // If M is odd countPalindromicStrings = (long)Math.Pow(N, (M - 1) / 2) * N; } // Count number of non-palindromic strings return (long)Math.Pow(N, M) - countPalindromicStrings; } static void Main(string[] args) { int N = 3, M = 2; Console.WriteLine(CountNonPalindromicStrings( N, M)); // Print the result }} |
Javascript
function countNonPalindromicString(N, M) { let countPalindromicStrings = 0; // Count number of palindromic strings if (M % 2 === 0) { // If M is even countPalindromicStrings = Math.pow(N, M / 2); } else { // If M is odd countPalindromicStrings = Math.pow(N, (M - 1) / 2) * N; } // Count number of // non-palindromic strings return Math.pow(N, M) - countPalindromicStrings;}const N = 3, M = 2;console.log(countNonPalindromicString(N, M)); |
Output
6
Time Complexity: O(log M).
Auxiliary Space: O(1), No Extra space is being used.
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!
