Sum of large exponents of 2

Question

I am trying to complete a coding challenge from hackerrank.com

Shashank is a newbie to mathematics, and he is very excited after knowing that a given l of cardinality N has (2^N - 1) non-empty sublist. He writes down all the non-empty sublists for a given set A. For each sublist, he calculates sublist_sum, which is the sum of elements and denotes them by S₁, S₂, S₃, ... , S_(2^N-1).

He then defines a special_sum, P.

P = 2^S₁ + 2^S₂ + 2^S₃ .... + 2^S_(2N-1) and reports P % (10^9 + 7).

OUPUT Print special_sum, P modulo (10^9 + 7).

I am near certain I have misunderstood the prompt, but my program is meant to receive a list of numbers. The program will raise 2 to the power of all combinations of this list (without duplicates, order doesn't matter, of all sizes), then sum them all together and print it.

The example from the website is

List 1, 1, 2 Ouput 44

Explanation

1. {1} and 2^1 = 2
2. {1} and 2^1 = 2
3. {2} and 2^2 = 4
4. {1,1} and 2^2 = 4
5. {1,2} and 2^3 = 8
6. {1,2} and 2^3 = 8
7. {1,1,2} and 2^4 = 16

So the total will be 44;

My understanding of merely summing the exponents together is wrong because the answer is much larger than the expected answer in the first test case (obviously).

Input 422 412 417 497 284 Output 67920854

Essentially, I want someone to explain the prompt. I think I'm just calculating the partial sum, but I don't know when or what I'm suppose to mod 10^9 + 7.

FYI I've only completed Algebra II, so if I've missed a mathematical concept, then keep my experience in mind when you explain it to me. I've been programming in C++, so code examples in the language is preferred.

Code My pitiful attempt at a solution: http://pastebin.com/c7YxCLMt

Answer 1

Without seeing your attempt, it's hard to say what might be the flaw but two things come to mind as possible pitfalls:

1. You mention that you are supposed to mod 10^9 + 7 but make sure you are doing mod (10^9 + 7)
2. The numbers you are calculating (2^497, 2^284, etc.) are enormous and would certainly overflow. If you are not handling this already, you might be able to improve your attempt by trying something like what they are doing here.

Edit: After looking over your code, it does appear that you are running into the overflow problem. You will benefit from incorporating the ideas here into your solution.

Answer 2

The question is essentially: given a list of numbers, find the sum of all possible products of 1 or more of the elements, where the list is not the list you're given but two to those powers. Your example is the sum of the products of one or more of {2, 2, 4}, for example.

We can simplify this further by looking at the sum of the products of 0 or more of the elements, and then subtracting 1 for the empty product we didn't want. This lets you use a neat trick: for each element in the list, you will either multiply by 1 or by the number. So with the list {2, 2, 4} the sum is (2+1)(2+1)(4+1) = 3*3*5 = 45, giving 45 - 1 = 44 as the answer.

---

Here's some working code in PARI/GP.

specialSum(v, m=10^9+7)=lift(factorback(apply(n -> Mod(2,m)^n+1, v))-1)

Usage:

specialSum([1,1,2])
specialSum([422,412,417,497,284])

Answer 3

Based on the comments above, I think you are not quite familiar of these algorithmic online judges. They are not the same with real life applications, they normally have extreme constrains which force you to use some clever tricks to handle it in time. (usually ~1 second)

---

For this question, the problem can be separated into two parts:

1. How to sum N^2 integers in time when N <= 10^5? (in 1 second)
2. How to calculate 2^x % M where x <= 10^5*10^10 = 10^15 in time? (in 1 second)

And of course, in the process, you cannot make any variable overflow, which is the reason why the problem asks you to output answer MOD 10^9 + 7 (I assume you know the basic properties of modular arithmetic.)

For point 1, the answer is, you can't. What I am trying to imply is that, there is some way that you can calculate the answer without summing N^2 items. I can give you a hints based on my accepted solution: Dynamic Programming, let DP(N) = required sum for items in array[0..N]. If you can formulate the DP recurrence, you can get the answer by summing only N integers, which can be calculated in time.

For point 2, you cannot do any naive linear pre-computation (use a for loop and times two of previous iteration, etc). By using DP mentioned in above, you only need to calculate 2^x % M where x <= 10^10, still the memory and the run time constrain will fail if you do that. Here you need another trick called Exponentiation by squaring which can compute 2^n in O(lg n), and thus acceptable.

---

Combine both point 1 & 2, you can solve this problem by Dynamic Programming & Exponentiation by squaring (& some basic modular arithmetic in between).