Count All Subsequences

Easy

0/40

0 upvote

Asked in company

Problem statement

You are given an array A of N integers. Your task is to find the total number of distinct subsequences that can be formed from this array.

A subsequence is a sequence that can be derived from the array by deleting some or no elements, without changing the relative order of the remaining elements. This includes the empty subsequence.

Since the answer can be very large, you must return the result modulo 10^9 + 7.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer N, the number of elements in the array.

The second line contains N space-separated integers, representing the elements of array A. (Note: The values of these integers do not affect the result).

Output Format:

Your function should return a single integer representing the total number of subsequences, modulo 10^9 + 7. The runner code will handle printing.

Notes:

For each of the N elements in the array, you have two choices: either include it in a subsequence or not include it. Since these choices are independent for each element, the total number of possible subsequences is 2 * 2 * ... * 2 (N times), which is 2^N. The problem is therefore equivalent to calculating 2^N mod (10^9 + 7). An efficient modular exponentiation algorithm is required to calculate this for large N.

Sample Input 1:

3
1 2 3

Sample Output 1:

Explanation for Sample 1:

With N=3 elements, there are 2^3 = 8 possible subsequences. These are:

{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}.

Sample Input 2:

4
10 4 8 2

Sample Output 2:

Explanation for Sample 2:

With N=4 elements, the total number of subsequences is 2^4 = 16. The specific values of the elements do not change this count.

Expected Time Complexity:

The expected time complexity is O(logN).

Constraints:

1 <= N <= 10^12
1 <= A[i] <= 10^9
Time Limit: 1 sec

Approaches (1)

Approach 1

Brute Force

Time Complexity

Space Complexity

(100% EXP penalty)

Count All Subsequences

Console