Given an integer N, the task is to find the probability that a number with a number of digits as N is a palindrome.
The number may have leading zeros.
Examples:
Input: N = 5
Output: 1 / 100
Input: N = 6
Output: 1 / 1000
Solution:
- As leading zeroes are allowed a total number of N digit numbers is 10N.
- A number is a palindrome when the first N/2 digits match with the last N/2 digits in reverse order.
- For an even number of digits, we can pick the first N/2 digits and then duplicate them to form the rest of N/2 digits so we can choose (N)/2 digits.
- For an odd number of digits, we can pick first (N-1)/2 digits and then duplicate them to form the rest of (N-1)/2 digits so we can choose (N+1)/2 digits.
- So the probability that an N digit number is palindrome is 10ceil( N / 2 ) / 10N or 1 / 10floor( N / 2 )
Below is the implementation of the approach:
C++
// C++ code of above approach#include <bits/stdc++.h>using namespace std;// Find the probability that a// n digit number is palindromevoid solve(int n){ int n_2 = n / 2; // Denominator string den; den = "1"; // Assign 10^(floor(n/2)) to // denominator while (n_2--) den += '0'; // Display the answer cout << 1 << "/" << den << "\n";}// Driver codeint main(){ int N = 5; solve(N); return 0;} |
Java
// Java code of above approachimport java.util.*;class GFG {// Find the probability that a// n digit number is palindromestatic void solve(int n){ int n_2 = n / 2; // Denominator String den; den = "1"; // Assign 10^(floor(n/2)) to // denominator while (n_2-- > 0) den += '0'; // Display the answer System.out.println(1 + "/" + den);}// Driver codepublic static void main(String[] args) { int N = 5; solve(N);}} // This code is contributed by Rajput-Ji |
Python3
# Python3 code of above approach # Find the probability that a # n digit number is palindrome def solve(n) : n_2 = n // 2; # Denominator den = "1"; # Assign 10^(floor(n/2)) to # denominator while (n_2) : den += '0'; n_2 -= 1 # Display the answer print(str(1) + "/" + str(den)) # Driver code if __name__ == "__main__" : N = 5; solve(N); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;class GFG {// Find the probability that a// n digit number is palindromestatic void solve(int n){ int n_2 = n / 2; // Denominator String den; den = "1"; // Assign 10^(floor(n/2)) to // denominator while (n_2-- > 0) den += '0'; // Display the answer Console.WriteLine(1 + "/" + den);}// Driver codepublic static void Main(String[] args) { int N = 5; solve(N);}} // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript implementation of the approach // Find the probability that a // n digit number is palindrome function solve(n) { let n_2 = parseInt(n / 2, 10); // Denominator let den; den = "1"; // Assign 10^(floor(n/2)) to // denominator while (n_2-- > 0) den += '0'; // Display the answer document.write(1 + "/" + den + "</br>"); } let N = 5; solve(N);// This code is contributed by divyeshrabadiya07.</script> |
1/100
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(1), as we are not using any extra space.
Approach:
Below is the implementation of the approach:
C++
// C++ implementation of the above approach#include <cmath>#include <iomanip>#include <iostream>using namespace std;// Function to calculate the probabilitystring calculateProbability(int N){ // Calculate the total number of N-digit numbers int totalNumbers = pow(10, N); // Initialize the count of palindromes int palindromeCount = 0; // Enumerate all palindromes with N digits for (int i = 0; i < totalNumbers; i++) { // Convert the number to string string number = to_string(i); // Pad the number with leading zeros if necessary while (number.length() < N) { number = "0" + number; } // Check if the number is a palindrome bool isPalindrome = true; for (int j = 0, k = N - 1; j < k; j++, k--) { if (number[j] != number[k]) { isPalindrome = false; break; } } // Increment the palindrome count if it's a // palindrome if (isPalindrome) { palindromeCount++; } } // Calculate the probability double probability = static_cast<double>(palindromeCount) / totalNumbers; // Convert probability to "1/100" format int numerator = 1; int denominator = 100; for (int i = 2; i <= 100; i++) { if (fmod(probability * 100, i) == 0 && fmod(denominator, i) == 0) { probability *= 100; denominator /= i; numerator *= (probability / 100); probability = fmod(probability, 100); } } // Create the output string string output = to_string(numerator) + "/" + to_string(denominator); return output;}// Driver Codeint main(){ int N = 5; string probability = calculateProbability(N); cout << probability << endl; return 0;} |
Java
import java.text.DecimalFormat;public class GFG { // Function to calculate the probability static String calculateProbability(int N) { // Calculate the total number of N-digit numbers int totalNumbers = (int) Math.pow(10, N); // Initialize the count of palindromes int palindromeCount = 0; // Enumerate all palindromes with N digits for (int i = 0; i < totalNumbers; i++) { // Convert the number to string String number = Integer.toString(i); // Pad the number with leading zeros if necessary while (number.length() < N) { number = "0" + number; } // Check if the number is a palindrome boolean isPalindrome = true; for (int j = 0, k = N - 1; j < k; j++, k--) { if (number.charAt(j) != number.charAt(k)) { isPalindrome = false; break; } } // Increment the palindrome count if it's a palindrome if (isPalindrome) { palindromeCount++; } } // Calculate the probability double probability = (double) palindromeCount / totalNumbers; // Convert probability to "1/100" format int numerator = 1; int denominator = 100; for (int i = 2; i <= 100; i++) { if (probability * 100 % i == 0 && denominator % i == 0) { probability *= 100; denominator /= i; numerator *= probability / 100; probability %= 100; } } // Create the output string DecimalFormat df = new DecimalFormat("#"); df.setMaximumFractionDigits(0); String output = df.format(numerator) + "/" + df.format(denominator); return output; } // Driver Code public static void main(String[] args) { int N = 5; String probability = calculateProbability(N); System.out.println(probability); }} |
Python3
def calculate_probability(N): # Calculate the total number of N-digit numbers total_numbers = 10 ** N # Initialize the count of palindromes palindrome_count = 0 # Enumerate all palindromes with N digits for i in range(total_numbers): # Convert the number to string number = str(i) # Pad the number with leading zeros if necessary while len(number) < N: number = "0" + number # Check if the number is a palindrome is_palindrome = True for j in range(0, N // 2): if number[j] != number[N - 1 - j]: is_palindrome = False break # Increment the palindrome count if it's a # palindrome if is_palindrome: palindrome_count += 1 # Calculate the probability probability = float(palindrome_count) / total_numbers # Convert probability to "1/100" format numerator = 1 denominator = 100 for i in range(2, 101): if probability * 100 % i == 0 and denominator % i == 0: probability *= 100 denominator //= i numerator *= (probability / 100) probability = probability % 100 # Create the output string output = str(numerator) + "/" + str(denominator) return outputif __name__ == "__main__": N = 5 probability = calculate_probability(N) print(probability) |
C#
using System;public class GFG{ // Function to calculate the probability public static string CalculateProbability(int N) { // Calculate the total number of N-digit numbers int totalNumbers = (int)Math.Pow(10, N); // Initialize the count of palindromes int palindromeCount = 0; // Enumerate all palindromes with N digits for (int i = 0; i < totalNumbers; i++) { // Convert the number to string string number = i.ToString(); // Pad the number with leading zeros if necessary while (number.Length < N) { number = "0" + number; } // Check if the number is a palindrome bool isPalindrome = true; for (int j = 0, k = N - 1; j < k; j++, k--) { if (number[j] != number[k]) { isPalindrome = false; break; } } // Increment the palindrome count if it's a palindrome if (isPalindrome) { palindromeCount++; } } // Calculate the probability double probability = (double)palindromeCount / totalNumbers; // Convert probability to "1/100" format int numerator = 1; int denominator = 100; for (int i = 2; i <= 100; i++) { if (probability * 100 % i == 0 && denominator % i == 0) { probability *= 100; denominator /= i; numerator *= (int)(probability / 100); probability = probability % 100; } } // Create the output string string output = numerator.ToString() + "/" + denominator.ToString(); return output; } // Driver Code public static void Main() { int N = 5; string probability = CalculateProbability(N); Console.WriteLine(probability); }} |
Javascript
// Function to calculate the probabilityfunction calculateProbability(N) { // Calculate the total number of N-digit numbers const totalNumbers = Math.pow(10, N); // Initialize the count of palindromes let palindromeCount = 0; // Enumerate all palindromes with N digits for (let i = 0; i < totalNumbers; i++) { // Convert the number to string let number = i.toString(); // Pad the number with leading zeros if necessary while (number.length < N) { number = "0" + number; } // Check if the number is a palindrome let isPalindrome = true; for (let j = 0, k = N - 1; j < k; j++, k--) { if (number[j] !== number[k]) { isPalindrome = false; break; } } // Increment the palindrome count if it's a palindrome if (isPalindrome) { palindromeCount++; } } // Calculate the probability const probability = palindromeCount / totalNumbers; // Convert probability to "1/100" format let numerator = 1; let denominator = 100; for (let i = 2; i <= 100; i++) { if (probability * 100 % i === 0 && denominator % i === 0) { probability *= 100; denominator /= i; numerator *= probability / 100; probability %= 100; } } // Create the output string const output = numerator + "/" + denominator; return output;}// Driver Codeconst N = 5;const probability = calculateProbability(N);console.log(probability); |
1/100
Time Complexity: O(N * 10^N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Find More on that Topic: geeksforgeeks.org/probability-that-a-n-digit-number-is-palindrome/ […]
… [Trackback]
[…] There you will find 32624 additional Info on that Topic: geeksforgeeks.org/probability-that-a-n-digit-number-is-palindrome/ […]
… [Trackback]
[…] Find More to that Topic: geeksforgeeks.org/probability-that-a-n-digit-number-is-palindrome/ […]