Проблема дня GFG [ 01 января 2023 ]

Для заданного числа n найдите количество всех двоичных последовательностей длины 2n, таких, что сумма первых n битов равна сумме последних n битов.
Ответ может быть очень большим. Итак, вы должны вернуть ответ по модулю 10 ^ 9 + 7.

Пример:

Input: n = 2
Output: 6
Explanation: There are 6 sequences of length 
2*n, the sequences are 0101, 0110, 1010, 1001, 
0000 and 1111.

Пример:

Input: n = 1
Output: 2
Explanation: There are 2 sequence of length 
2*n, the sequence are 00 and 11.

Ваша задача
Вам не нужно ничего читать или печатать. Ваша задача состоит в том, чтобы завершить функцию compute_value(), которая принимает n в качестве входного параметра и возвращает количество всех двоичных последовательностей длины 2*n, таких что сумма первых n бит равна сумме последних n бит по модулю 10^9 + 7.

Ожидаемая временная сложность:O(n * log(n))
Ожидаемая пространственная сложность:O(1)

Решение

class Solution {
    public long power(long x, long y, long p) {
        long res = 1l;
        x = x % p;
        while (y > 0) {
            if (y % 2 == 1)
                res = (res * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    public long modInverse(long n, long p) {
        return power(n, p - 2, p);
    }
    
    public int compute_value(int n) {
        // code here
        long ans = 1l;
        long mod = (long)(Math.pow(10, 9) + 7l);
        long compute = 1l;
        for(int i=0;i<n;i++) {
            compute = (compute%mod * (long)(n-i)%mod) % mod;
            compute = (compute%mod * modInverse(i+1, mod)%mod) % mod;
            ans = (ans%mod + (compute%mod*compute%mod)%mod) % mod;
        }
        return (int)(ans%mod);
    }
}

Временная сложность: O(N*logN), потому что мы вычисляем мощность на каждой итерации, которая занимает O(logN) времени.

Пространственная сложность: O(1)

Присоединяйтесь к моему каналу Telegram, чтобы получить все решения GFG POD.



ЕДИНСТВЕННЫЙ МАСТЕР | КОДИРОВАНИЕ
кодирование #программирование #leetcode #codechef #hackerrank #interviewbit #gfgt.me



https://t.me/sole_master_coding

Спасибо всем!!!

С Новым годом!!!