Contar números que tienen N 0 y M 1 sin ceros a la izquierda

Dados dos enteros N y M , la tarea es encontrar el número de números distintos que tienen N 0 y M 1 sin ceros a la izquierda y N + M dígitos totales.

Ejemplos:  

Entrada: N = 2, M = 2 
Salida: 3 
Los números son 1001, 1010 y 1100.

Entrada: N = 2, M = 3 
Salida: 6 
Los números son 10011, 10101, 10110, 11001, 11010 y 11100. 
 

Enfoque: el problema se puede resolver fácilmente encontrando la permutación total de N elementos similares y M – 1 elementos similares. Como no se permiten ceros a la izquierda, siempre se fija un 1 al principio del número. Los restantes M – 1 1 y N 0 están dispuestos en diferentes permutaciones. ¡ Ahora, el número de permutaciones de (A + B) objetos donde A objetos del mismo tipo y B objetos de otro tipo está dado por (A + B)! / (A! * B!) . Por lo tanto, el número de números distintos viene dado por (N + M -1)! / (N! * (M – 1)!) .

A continuación se muestra la implementación del enfoque anterior: 

// 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 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 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# 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 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..
?>

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

10

Complejidad de tiempo: O(N+M)
Espacio auxiliar: O(1), ya que no se utiliza espacio adicional