# Total Number of Graphs Possible (HELP!)

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 â€¦??

I guess the answer should just be 2^n, as for each vertice you have two options: Select/ Not select

So for n vertices answer should be 22â€¦2=2^n

Can the connected components be rearranged?

For example, is the graph `1 -> 2 -> 3` is different from `2 -> 1 -> 3`?

I think all the vertices should be included, but the edges can be different.

Did you by any chance do
2^(n*(n-1)/2 % mod) ?

2 Likes

@dormordo For n=4 answer was 64

@crap_the_coder Yes i think because each will generate new graph and in example output answer for n = 4 was 64

@everule1 Yes i applied same formula and it passed 5 out of 13 test cases, is it related to modular exponentiationâ€¦?

Im sorry, but that is wrongâ€¦

1 Like

You can take %(mod -1)
I think you should read fermatâ€™s little theorem

i know fermatâ€™s little theorem but how is it useful in this caseâ€¦??

Let 10^9 + 7 =p
Now say
You want 2^p+3
You take 2^3 =8 but 2^p+3 is 16 mod p
Because 2^p is 2 mod p.

But i have to take mod with overall value
i.e
let x = (n*(n-1))/2;

then what i was calculating is (2^x)%mod

1 Like

Please just post the code you submitted, as best as you can remember it

#include<bits/stdc++.h>
using namespace std;

#define ll long long int
const ll MOD = 1e9 + 7;

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;
``````

}

1 Like

Since `n` is declared as an `int`, this will overflow for sufficiently large `n`: n=46342 should do the trick.

3 Likes

i had tried to declare it long long int also but it didnâ€™t helped much, so what should i have done here then â€¦??

Declaring `n` as `long long int` would eliminate one source of error, and I canâ€™t see any others offhand.

Edit:

Wait - why â€ś`- 1`â€ť here?

``````b = (b * 10 + (sb[i] - '0')) % (MOD - 1);
``````

Edit2:

Actually, you shouldnâ€™t be taking the exponent modulo anything - just leave it alone.

Edit3:

Oh, I think I see. Hmmm â€¦ canâ€™t find any further errors after you change `n` to be `long long int`.

2 Likes

Idk doesnâ€™t give the right answer for 10^9 on codechef ide

What is the right answer? I get

``````2097152
``````

but may have made a mistake.

2 Likes