Horje
Count the number of Binary Strings which have X 1's and Y 0's

Given two integers X and Y, the task is to count the number of binary strings which have X 1’s and Y 0’s and there are no two consecutive 1’s in the string.

Examples:

Input: X = 2, Y = 2
Output: 3
Explanation: 1010, 0101, 1001 – these are 3 strings that can be possible such that there are no two consecutive 1’s.

Input: X = 5, Y = 3
Output: 0
Explanation: There is no such string that can be possible.

Approach: This can be solved with the following idea:

First calculating factorial of both the given numbers and then calculating power of each one will led us to get the desired answer.

Below are the steps involved:

  • Calculating rem Y – X + 1.
    • if rem < 0, return 0.
  • Calculate the factorial of Y+1 and X by calling ncr function.
  • Also, found out the power of both numbers using the binpow function.
  • For the answer, multiply the factorial of X with the power of y.
  • Then final, multiply answer with power of X.
  • Return answer.

Below is the implementation of the code:

C++

// C++ Implementation
#include <bits/stdc++.h>
using namespace std;
 
int mod = 1e9 + 7;
 
// Function to calculate power a^b
long long binpow(long long a, long long b)
{
    long long ans = 1;
    while (b) {
        if (b % 2 == 1) {
            ans = (ans * a) % mod;
        }
        a = (a * a) % mod;
        b = b / 2;
    }
    return ans;
}
 
// Function to calculate combinations
long long ncr(long long a, long long b)
{
    // Intialising factorial of a, b, c
    long long facta = 1;
    long long factb = 1;
    long long factab = 1;
 
    // Iterating for a
    for (int i = a; i >= 1; i--) {
 
        facta = (facta * i);
    }
 
    // Iterating for b
    for (int j = b; j >= 1; j--) {
 
        factb = (factb * j);
    }
 
    long long x = (a - b);
 
    // Iterating for factorial ab
    for (int i = x; i >= 1; i--) {
 
        factab = (factab * i);
    }
 
    // calculting power
    long long invab = binpow(factab, mod - 2);
    long long invb = binpow(factb, mod - 2);
 
    long long answer = (facta * invb) % mod;
    answer = (answer * invab) % mod;
 
    // Return ans
    return answer;
}
 
// Function to count number of strings
// that can be constructed
int CountString(int x, int y)
{
 
    // Calculate rem
    long long rem = y - x + 1;
 
    // If rem is negative means no one is there
    if (rem < 0) {
        return 0;
    }
 
    // Calculate combinations
    long long answer = ncr(y + 1, x);
 
    // Return answer
    return answer;
}
 
// Driver code
int main()
{
 
    int x = 2;
    int y = 2;
 
    // Function call
    cout << CountString(x, y);
    return 0;
}

Java

import java.util.*;
 
public class CountString {
 
    static long mod = 1000000007;
 
    // Function to calculate power a^b
    static long binpow(long a, long b) {
        long ans = 1;
        while (b > 0) {
            if (b % 2 == 1) {
                ans = (ans * a) % mod;
            }
            a = (a * a) % mod;
            b /= 2;
        }
        return ans;
    }
 
    // Function to calculate combinations
    static long ncr(long a, long b) {
        // Initializing factorial of a, b, c
        long facta = 1;
        long factb = 1;
        long factab = 1;
 
        // Iterating for a
        for (long i = a; i >= 1; i--) {
            facta = (facta * i) % mod;
        }
 
        // Iterating for b
        for (long j = b; j >= 1; j--) {
            factb = (factb * j) % mod;
        }
 
        long x = a - b;
 
        // Iterating for factorial ab
        for (long i = x; i >= 1; i--) {
            factab = (factab * i) % mod;
        }
 
        // calculating power
        long invab = binpow(factab, mod - 2);
        long invb = binpow(factb, mod - 2);
 
        long answer = (facta * invb) % mod;
        answer = (answer * invab) % mod;
 
        // Return ans
        return answer;
    }
 
    // Function to count the number of strings that can be constructed
    static int countString(int x, int y) {
        // Calculate rem
        long rem = y - x + 1;
 
        // If rem is negative means no one is there
        if (rem < 0) {
            return 0;
        }
 
        // Calculate combinations
        long answer = ncr(y + 1, x);
 
        // Return answer
        return (int) answer;
    }
 
    // Driver code
    public static void main(String[] args) {
        int x = 2;
        int y = 2;
 
        // Function call
        System.out.println(countString(x, y));
    }
}

Python3

# Python Implementation
 
mod = 10**9 + 7
 
# Function to calculate power a^b
def binpow(a, b):
    ans = 1
    while b > 0:
        if b % 2 == 1:
            ans = (ans * a) % mod
        a = (a * a) % mod
        b = b // 2
    return ans
 
# Function to calculate combinations
def ncr(a, b):
    # Initialize factorial of a, b, and (a-b)
    facta = 1
    factb = 1
    factab = 1
 
    # Iterating for a
    for i in range(a, 0, -1):
        facta = (facta * i)
 
    # Iterating for b
    for j in range(b, 0, -1):
        factb = (factb * j)
 
    x = a - b
 
    # Iterating for factorial (a-b)
    for i in range(x, 0, -1):
        factab = (factab * i)
 
    # Calculate powers
    invab = binpow(factab, mod - 2)
    invb = binpow(factb, mod - 2)
 
    answer = (facta * invb) % mod
    answer = (answer * invab) % mod
 
    # Return the answer
    return answer
 
# Function to count the number of strings
# that can be constructed
def CountString(x, y):
    # Calculate rem
    rem = y - x + 1
 
    # If rem is negative, no valid strings can be formed
    if rem < 0:
        return 0
 
    # Calculate combinations
    answer = ncr(y + 1, x)
 
    # Return the answer
    return answer
 
# Driver code
x = 2
y = 2
 
# Function call
print(CountString(x, y))

C#

// C# Implementation
using System;
 
public class GFG {
    static int mod = 1000000007;
 
    // Function to calculate power a^b
    static long binpow(long a, long b)
    {
        long ans = 1;
        while (b > 0) {
            if (b % 2 == 1) {
                ans = (ans * a) % mod;
            }
            a = (a * a) % mod;
            b = b / 2;
        }
        return ans;
    }
 
    // Function to calculate combinations
    static long ncr(long a, long b)
    {
        // Initializing factorial of a, b, c
        long facta = 1;
        long factb = 1;
        long factab = 1;
 
        // Iterating for a
        for (int i = (int)a; i >= 1; i--) {
            facta = (facta * i);
        }
 
        // Iterating for b
        for (int j = (int)b; j >= 1; j--) {
            factb = (factb * j);
        }
 
        long x = (a - b);
 
        // Iterating for factorial ab
        for (int i = (int)x; i >= 1; i--) {
            factab = (factab * i);
        }
 
        // calculating power
        long invab = binpow(factab, mod - 2);
        long invb = binpow(factb, mod - 2);
 
        long answer = (facta * invb) % mod;
        answer = (answer * invab) % mod;
 
        // Return answer
        return answer;
    }
 
    // Function to count the number of strings that can be
    // constructed
    static int CountString(int x, int y)
    {
        // Calculate rem
        long rem = y - x + 1;
 
        // If rem is negative means no one is there
        if (rem < 0) {
            return 0;
        }
 
        // Calculate combinations
        long answer = ncr(y + 1, x);
 
        // Return answer
        return (int)answer;
    }
 
    // Driver code
    static void Main()
    {
        int x = 2;
        int y = 2;
 
        // Function call
        Console.WriteLine(CountString(x, y));
    }
}
 
// This code is contributed by Susobhan Akhuli

Javascript

// Javascript program for the above approach
const mod = BigInt(10**9 + 7);
 
// Function to calculate power a^b
function binpow(a, b) {
    let ans = BigInt(1);
    while (b > 0n) {
        if (b % 2n === 1n) {
            ans = (ans * BigInt(a)) % mod;
        }
        a = (BigInt(a) * BigInt(a)) % mod;
        b = b / 2n;
    }
    return ans;
}
 
// Function to calculate combinations
function ncr(a, b) {
    // Initialize factorial of a, b, and (a-b)
    let facta = BigInt(1);
    let factb = BigInt(1);
    let factab = BigInt(1);
 
    // Iterating for a
    for (let i = BigInt(a); i >= 1n; i--) {
        facta = (facta * i) % mod;
    }
 
    // Iterating for b
    for (let j = BigInt(b); j >= 1n; j--) {
        factb = (factb * j) % mod;
    }
 
    let x = BigInt(a - b);
 
    // Iterating for factorial (a-b)
    for (let i = x; i >= 1n; i--) {
        factab = (factab * i) % mod;
    }
 
    // Calculate powers
    let invab = binpow(factab, mod - 2n);
    let invb = binpow(factb, mod - 2n);
 
    let answer = (facta * invb) % mod;
    answer = (answer * invab) % mod;
 
    // Return the answer
    return answer;
}
 
// Function to count the number of strings that can be constructed
function countString(x, y) {
    // Calculate rem
    let rem = BigInt(y - x + 1);
 
    // If rem is negative, no valid strings can be formed
    if (rem < 0n) {
        return 0;
    }
 
    // Calculate combinations
    let answer = ncr(BigInt(y + 1), BigInt(x));
 
    // Return the answer
    return Number(answer);
}
 
// Driver code
const x = 2;
const y = 2;
 
// Function call
console.log(countString(x, y));
 
// This code is contributed by Susobhan Akhuli

Output

3

Time Complexity: O(n*log n)
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Bitwise OR Triplets in a Binary String Bitwise OR Triplets in a Binary String
Spanning Tree vs Minimum Spanning Tree Spanning Tree vs Minimum Spanning Tree
How to Pass a String to a Function using Call by Reference? How to Pass a String to a Function using Call by Reference?
How to Declare &amp; Initialise a String in different Programming languages? How to Declare &amp; Initialise a String in different Programming languages?
3 Ways for Traversal of Strings 3 Ways for Traversal of Strings

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 14



 

Horje