Probability that a N digit number is palindrome

0 0 7 minutes read

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 10^N.
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 10^{ceil( N / 2 )} / 10^N or 1 / 10^{floor( 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 palindrome
void 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 code
int main()
{
 
    int N = 5;
 
    solve(N);
 
    return 0;
}

Java

// Java code of above approach
import java.util.*;
 
class GFG 
{
 
// Find the probability that a
// n digit number is palindrome
static 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 code
public 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 approach
using System;
 
class GFG 
{
 
// Find the probability that a
// n digit number is palindrome
static 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 code
public 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>

Output

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 probability
string 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 Code
int 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 output
 
 
if __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 probability
function 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 Code
const N = 5;
const probability = calculateProbability(N);
console.log(probability);

Output

1/100

Time Complexity: O(N * 10^N)
Auxiliary Space: O(N)

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 zambiatek!