Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 2 Aug, 2020

Moderate

```
As this value might be large, print it modulo 10^9 + 7
```

```
The first line contains an integer 'T' which denotes the number of test cases. Then the test cases follow :
The first line of each test case contains an integer 'N' representing the size of the array/list.
The second line contains 'N' single space - separated integers representing the elements of the array.
```

```
For each test case, print the total number of subsequences in which all elements are equal.
The output of each test case will be printed in a separate line.
```

```
You don't need to print anything. It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 100
1 <= N <= 10^5
0 <= ARR[i] <= 10^9
Time Limit : 1 sec
```

The idea is to generate all the subsequences and check whether the elements present are equal or not.

Here is the algorithm :

- Generate all the subsequences of the given array.
- Maintain a variable â€˜COUNTâ€™ which stores the total number of subsequences in which all the elements are equal.
- Iterate over each of the generated subsequences.
- In case all the elements of the current subsequence are equal, we increment â€˜COUNTâ€™.

- After, iterating over all the subsequences, the value of â€˜COUNTâ€™ is the answer that we are looking for.

In this approach, we will calculate the contribution of each distinct element to the answer. For example, if we had â€˜kâ€™ occurrences of an element in the array, we will be able to form :

- kC1 subsequences of length 1
- kC2 subsequences of length 2
- kC3 subsequences of length 3

.

.

.

K. kCk subsequences of length k

Hence the contribution of this element to the answer = kC1 + kC2 + kC3 â€¦ + kCk = (2^k) - 1

So, the contribution of each distinct element would be equal to (2 ^ FREQ) - 1. Where â€˜FREQâ€™ is the frequency of that element in the array.

Here is the algorithm :

- Store the frequency of each element in a hashmap (say, â€˜FREQâ€™).
- Maintain a variable â€˜RESULTâ€™ which stores the final answer.
- For each element present in the hashmap,
- Calculate the value of (2^eleCount - 1) % MOD, â€˜eleCountâ€™ is frequency of current element.
- Add the above value to â€˜RESULTâ€™

- The final answer is the value of â€˜RESULTâ€™ after we are done iterating over all the elements of the hashmap.