- Practice
- Mathematics
- Algebra
- Shashank and List
- Discussions

# Shashank and List

# Shashank and List

chetan8984 + 10 comments Best solution would be to use formula (a+1)(b+1)(c+1)-1 = a+b+c+ab+bc+ca+abc

kira1kira22 + 1 comment you're a genius !!! how did you get with this idea ?

chetan8984 + 2 comments if I post it here, it may violate the rules. better I'll send u a msg.

123Suraj + 0 comments Could u plz explain the logic?

rohitnarayan + 0 comments can u plz msg me the logic

PRATEEK_1 + 0 comments Really nice method.

Rpaann + 1 comment very nice, thank you!

mhlaskar1991 + 0 comments [deleted]

SalvadorDali + 1 comment Based on the explanation you mean subsets of a set, not sublists of a list. Can you properly clarify this?

amititkgpChallenge Author + 0 comments Sublist of list.

Nightman463 + 3 comments This is the body of my main method, which passed all test cases.

`Scanner sc = new Scanner(System.in); int size = sc.nextInt(); long sum = 0; while(sc.hasNextBigInteger()) { BigInteger n = sc.nextBigInteger(); BigInteger b = BigInteger.valueOf(2).modPow(n, BigInteger.valueOf(1000000007)); long ans = b.intValue()*(sum+1)+sum; sum = (long)ans%1000000007; } System.out.println((long)sum);`

jayaprakash_a + 0 comments could you explain the logic

mhlaskar1991 + 2 comments Please explain the logic

Nightman463 + 0 comments [deleted]Nightman463 + 0 comments Basically it just takes the last line of the editorial and does that in a loop.

"So final answer will be (2^a[1] + 1) * (2^a[2] + 1)* ........ *(2^a[n] + 1) - 1."

The fancy stuff like the big integer stuff and the type conversions are just there to help pass some of the bigger test cases I believe.

vikramvarun + 0 comments I have used slightly different approcach, but was getting timeout on some cases. Using modPow instead of pow helped. I wasn't even aware of this direct methos. Thanks.

prithvirajbilla + 3 comments Please chek my approach. Let say the set A = {a1,a2,a,3,a4.. an};

a1 | a2 a1a2 | a3 a1a3 a2a3 a1a2a3 | ....

the answer for the one element is ans[1]; ans[2] = 2^a1 + 2^a2 + (2^a1 * 2^a2); ans[2] = ans[1] + a^a2 +(ans[1]*2^a2); => ans[i] = ans[i-1](2^i + 1) + 2^i.

But in the editorial, it is mentioned as somewhat different.

aditya730 + 0 comments Yes,my approach is exactly the same but i'm only getting 2 test cases right.

Shuboy2014 + 0 comments Author you need to clarify the doubt .

larics + 0 comments Your approach is absolutely correct (with only comment, that it should be

ans[i] = ans[i-1](2^ai + 1) + 2^ai

instead of

ans[i] = ans[i-1](2^i + 1) + 2^i),

which is just a misprint, I suppose).

And it can be converted as:

ans[i-1](2^a[i] + 1) + 2^a[i] =

= ans[i-1](2^a[i] + 1) + (2^a[i] + 1) - 1 =

= (2^a[i] + 1)(ans[i-1] + 1) - 1 = ... =

= (2^a[i] + 1)(2^a[i-1] + 1)...(2^a[2] + 1)(ans[1] + 1) - 1 =

= (2^a[i] + 1)(2^a[i-1] + 1)...(2^a[2] + 1)(2^a[1] + 1) - 1,

which is exactly what editorial has.

One thing I don't agree with the editorial is "Ans as we know, Answer for null set is 1". So, I used ans[1] as a base. And it will be better if editorial wouldn't contain typos.

imran_buet78 + 1 comment My code is giving timeout on case 7,8,9,10. can anyone help?

import sys import math T = int(input()) N=[] res=1 n=input().strip().split(' ') for j in n : N.append(int(j)) for i in N: res=res*(2**i+1)%(10**9 + 7) print(res-1)

vinayb21 + 2 comments 2**i does calculate the exponentiation in O(n) time. If you use build in function in math library math.pow(x,n) then it calculates the power in O(logn) time. You can also create your own power function to calculate in O(logn) time.

Limeeattack + 0 comments [deleted]Limeeattack + 0 comments Since we're looking at powers of 2 just use bitshift, that is faster since it doesn't have the overhead of a function call. Also there is no need for calculating 10**9+7 every time, since it's a constant. Just write 1000000007 instead.

Sort 13 Discussions, By:

Please Login in order to post a comment