TMP - editorial

Practice
ALGO2020

Editorialist: akshayakgec

DIFFICULTY:

EASY

PREREQUISITES:

MATHS

PROBLEM:

You just have to find the all the possible subsets in a given set.

QUICK EXPLANATION:

The count of all the subset in a set is 2^n.

EXPLANATION:

We just have to count the total subsets of an array of size n which is equal to 2^n but we are not including an empty set so the answer will be (2^n)-1.

We can use Binary exponentiation to find 2^n and take modulo at each step to prevent range overflow.

Editorialist's Solution
#define ll long long
#define mod 1000000007
using namespace std;
ll power(ll x,ll y)
{
   ll res = 1;  
   while (y > 0)
   {
       if (y & 1)
       {
           res = ((res % mod) * (x % mod)) % mod;
       }
       y = y >> 1;
       x = ((x % mod) * (x % mod)) % mod;
   }
   return res;
}
int main() {
  int t; cin >> t;
  while(t--) {
      ll n; cin >> n;
      ll ans = power(2, n);
      ans = (ans - 1 + mod) % mod;
      cout << ans << "\n";
   }
   return 0;
}