Count numbers having N 0’s and M 1’s with no leading zeros

0 0 4 minutes read

Given two integer N and M, the task is to find the number of distinct numbers having N 0’s and M 1’s with no leading zeros and N + M total digits.

Examples:

Input: N = 2, M = 2
Output: 3
The numbers are 1001, 1010 and 1100.

Input: N = 2, M = 3
Output: 6
The numbers are 10011, 10101, 10110, 11001, 11010 and 11100.

Approach: The problem can be easily solved by finding the total permutation of N similar items and M – 1 similar items. Since no leading zeros are allowed, one 1 is always fixed at the start of the number. The remaining M – 1 1’s and N 0’s are arranged in different permutations. Now, the number of permutations of (A + B) objects where A objects of the same type and B objects of other type is given by (A + B)! / (A! * B!). Therefore, the number of distinct numbers is given by (N + M -1)! / (N! * (M – 1)!).

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
// Function to return the factorial of a number
ll factorial(int f)
{
    ll fact = 1;
 
    for (int i = 2; i <= f; i++)
        fact *= (ll)i;
 
    return fact;
}
 
// Function to return the count of distinct
// (N + M) digit numbers having N 0's
// and  M 1's with no leading zeros
ll findPermutation(int N, int M)
{
    ll permutation = factorial(N + M - 1)
                     / (factorial(N) * factorial(M - 1));
    return permutation;
}
 
// Driver code
int main()
{
    int N = 3, M = 3;
    cout << findPermutation(N, M);
 
    return 0;
}

Java

// Java implementation of the approach
import java.io.*;
 
class GFG
{
// Function to return the factorial of a number
static int factorial(int f)
{
    int fact = 1;
 
    for (int i = 2; i <= f; i++)
        fact *= (int)i;
 
    return fact;
}
 
// Function to return the count of distinct
// (N + M) digit numbers having N 0's
// and  M 1's with no leading zeros
static int findPermutation(int N, int M)
{
    int permutation = factorial(N + M - 1)
                    / (factorial(N) * factorial(M - 1));
    return permutation;
}
 
// Driver code
public static void main (String[] args)
{
 
    int N = 3, M = 3;
    System.out.println(findPermutation(N, M));
}
}
 
// This code is contributed
// by ajit

Python3

# Python3 implementation of the approach
 
# Function to return the factorial
# of a number
def factorial(f):
    fact = 1
    for i in range(2, f + 1):
        fact *= i
    return fact
 
# Function to return the count of distinct
# (N + M) digit numbers having N 0's
# and  M 1's with no leading zeros
def findPermuatation(N, M):
    permutation = (factorial(N + M - 1) //
                  (factorial(N) * factorial(M - 1)))
    return permutation
 
# Driver code
N = 3; M = 3
print(findPermuatation(N, M))
 
# This code is contributed 
# by Shrikant13

C#

// C# implementation of the approach
using System;
 
class GFG
{
// Function to return the factorial of a number
static int factorial(int f)
{
    int fact = 1;
 
    for (int i = 2; i <= f; i++)
        fact *= (int)i;
 
    return fact;
}
 
// Function to return the count of distinct
// (N + M) digit numbers having N 0's
// and  M 1's with no leading zeros
static int findPermutation(int N, int M)
{
    int permutation = factorial(N + M - 1)
                    / (factorial(N) * factorial(M - 1));
    return permutation;
}
 
// Driver code
public static void Main()
{
    int N = 3, M = 3;
    Console.Write(findPermutation(N, M));
}
}
 
// This code is contributed
// by Akanksha Rai

PHP

<?php
 
// PHP implementation of the approach
// Function to return the factorial of a number
function factorial($f)
{
    $fact = 1;
 
    for ($i = 2; $i <= $f; $i++)
        $fact *= $i;
 
    return $fact;
}
 
// Function to return the count of distinct
// (N + M) digit numbers having N 0's
// and  M 1's with no leading zeros
function findPermutation($N,$M)
{
    $permutation = factorial($N + $M - 1)
                    / (factorial($N) * factorial($M - 1));
    return $permutation;
}
 
    // Driver code
    $N = 3;
    $M = 3;
    echo findPermutation($N, $M);
     
// This code is contributed by ajit.. 
?>

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to return the factorial of a number
function factorial(f)
{
    var fact = 1;
 
    for(var i = 2; i <= f; i++)
        fact *= i;
 
    return fact;
}
 
// Function to return the count of distinct
// (N + M) digit numbers having N 0's
// and  M 1's with no leading zeros
function findPermutation(N, M)
{
    var permutation = factorial(N + M - 1) / 
                    (factorial(N) * factorial(M - 1));
    return permutation;
}
 
// Driver code
var N = 3, M = 3;
 
document.write(findPermutation(N, M));
 
// This code is contributed by noob2000
 
</script>

Output:

Time Complexity: O(N+M)
Auxiliary Space: O(1), as no extra space is 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 zambiatek!