- 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]

mhlaskar1991 + 0 comments Please explain the logic

sraman915 + 0 comments [deleted]KAUSHIKVRM + 0 comments pls msg me and explain your logic

rohanakar + 0 comments genius man.. genius

psshah + 0 comments plz describe derevation of this clue.

ankityadav2242 + 0 comments # include

using namespace std; int m=1000000000+7;

long power(unsigned long long a,int n) { if(n==0) return 1; if(n%2==0) return (power((a%m*a%m)%m,n/2))%m; else { return (a%m*power((a%m*a%m)%m,n/2)%m)%m; } }

int main() { int n; cin>>n; long a=1; vector ans; int arr[n]; for(int i=0;i>arr[i]; ans.push_back(1+power(2,arr[i]));

`} for(int i=0;i<n;i++) { a=(ans[i]%m * a%m)%m; } cout<<a-1;`

}

khoangcachxalam1 + 0 comments good idea ! thanks you

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.

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.

anoNMS + 2 comments can anyone tell me... whats with this %(10^9+7) all the time man....

lagahrajan + 0 comments 2,147,483,647 is max value of int in c++ and java (may b in other language also ) so when %(10^9+7) u can always store that value in int (as %(10^9+7)<10^9+7< 2,147,483,647 ) and your ans will not be unexpected (provided your logic is correct). hope this help;

simon_wilkinson + 1 comment Also 10^9+7 is prime, which means we can make use of Fermat's little theorem. It is essential for this question, for example in python: doing pow(x, y, z) as opposed to x**y % z is much more efficient because it takes advantage of Fermat's little theorem.

lagahrajan + 0 comments good point and thanks for great info.

Saras_Arya + 1 comment I can't understand the rational behind the solution. How did you derive the result (2^a[i] + 1) and then multiply all the solutions and not add them. I have been trying to wrap my head around this, but not able to get it. Would be great if someone can explain me how they thought about this problem.

simon_wilkinson + 0 comments Normally I don't agree with posting explanations in the discussion section, but since the editorial is so poorly explained here is my attempt:

To explain the solution, consider the list {a,b,c} with sublist sums a, b, c, a+b, a+c, b+c, a+b+c.

Doing 2 to the power of these numbers, and writing A = 2^a, and using 2^(a+b) = 2^a * 2^b

A, B, C, AB, AC, BC, ABC

So P = A + B + C + AB + AC + BC + ABC = (1 + A)(1 + B)(1 + C) - 1

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.

sahildua2305 + 0 comments Can anyone please check my solution and suggest how can I optimize the solution to get AC for last 4 large test cases?

sonupanchal + 1 comment why my solution get time out in some cases. i dont think it is different from editorial solution #include #include

`int power(long long int a) { long long int i,s=1; if(a==0) return 1; for(i=0;i<a;i++) { s=(2*s)%1000000007; } return s; } int main() { int i,n; long long int a[100000]={0},s=1; scanf("%d",&n); for(i=0;i<n;i++) scanf("%lld",&a[i]); for(i=0;i<n;i++) { s=s*(power(a[i])+1); s=s%1000000007; } s--; printf("%lld",s); return 0; }`

nikhilksingh97 + 0 comments power function is not that efficient!!!

svdamani + 0 comments Python 3 solution works fine:

`from functools import reduce _, m = input(), 10 ** 9 + 7 print(reduce(lambda a, b: a * b % m, [1 + pow(2, int(x), m) for x in input().split()], 1) - 1)`

No more comments

Sort 10 Discussions, By:

Please Login in order to post a comment