There was problem given to be in a hiring challenge which i was not able to solve completely so i am just curious to know what i missed.
Problem statement:
Given a number of vertices (n), determine the number of ways these vertices can form a graph, the graph can be disjoint so it is not necessary to connect all vertices. The answer can be very large so return modulo 10^9+7 ;
Constrains: 1 < n < 10^9
What i did is used the formula 2^(n*(n-1)/2) to get number of all possible graphs and used modular exponentiation to compute value, but i was not able to pass all test cases.
Can anyone tell me what i did wrong or is it some other concept to be used …??
ll powerLL(ll x, ll n)
{
ll ans = 1;
while (n) {
if (n & 1)
ans = ans * x % MOD;
n = n / 2;
x = x * x % MOD;
}
return ans;
}
ll powerStrings(string sa, string sb)
{
ll a = 0, b = 0;
for (int i = 0; i < sa.length(); i++)
a = (a * 10 + (sa[i] - '0')) % MOD;
for (int i = 0; i < sb.length(); i++)
b = (b * 10 + (sb[i] - '0')) % (MOD - 1);
return powerLL(a, b);
}
int main()
{
int n; cin>>n;
ll tmp = (n*(n-1))/2;
string p = to_string(tmp);
cout << powerStrings("2", p) << endl;
return 0;