Request on checking this proof for REDONE MAY19B

For any three numbers x,y,z from the list.

Take any two you get x + y +xy = (1+x)(1+y) - 1
Take (1+x)(1+y) - 1 with z and get (((1+x)(1+y) - 1) + 1)(1+z) - 1
So combining any three numbers will give formula (1+x)(1+y)(1+z) - 1
By induction can we prove for combining list of any n numbers in ANY order its (1+x1)(1+x2)(1+x3)……(1+xn) - 1?

1 Like

Yes…by combining n numbers will give same formula but you have to pre-compute for all n to avoid TLE.

Have I proved here that order doesn’t matter?

Order does not matter in case of multiplication.
You can use your formula for this problem. It’ll work fine.

This is a super-easy problem . I don’t know why people are investing so much time for its proof since last 2 weeks(most of the people who solved it didn’t derive any proof for it in the contest, nor should you,if you want to save time in contest!) , my advice is:- Invest time in better problems if you guys want improvement!! :slight_smile:

3 Likes

History repeats itself
its like last time where people were trying to solve Fences prob without maps. Whats funny is that indirectly they were implementing maps anyways
thats jst overkill

2 Likes

I am still wondering, what you are saying, multiplying them is same as (1+n)!, where n is the largest number in your series, starting from (x1 to xn) and yes it exceeds Time Limit, if you find factorial of numbers like 1000000, thousands of times.
Your formula at last will give (1+n)!-1.

I say lets close it :grin:

1 Like

Yes please!!!:joy:!!!