HackerRank Algebra – Shashank and List

Challenge: Shashank and List

Subdomeniu: Algebra (algebra)

Scor cont: 20.0 / 20

Submission status: Accepted

Submission score: 1.0

Submission ID: 464740228

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/shashank-and-list/problem

Cerinta

Shashank is a newbie to mathematics, and he is very excited after knowing that a given l of cardinality _N_ has (_2<sup>N</sup> - 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<sub>1</sub>, S<sub>2</sub>, S<sub>3</sub>, ... , S<sub>(2<sup>N</sup>-1)</sub>.

He then defines a special\_sum, _P_.

P = 2<sup>S<sub>1</sub> </sup> + 2<sup>S<sub>2</sub> </sup> + 2<sup>S<sub>3</sub> </sup> .... + 2<sup>S<sub>(2<sup>N</sup>-1)</sub> </sup>and reports P % (10<sup>9</sup> + 7).  

**Input Format**  
The first line contains an integer _N_, i.e., the size of list _A_.  
The next line will contain _N_ integers, each representing an element of list _A_.  

**Output Format**  
Print special\_sum, P _modulo (10<sup>9</sup> + 7)_.  

**Constraints**  
1 ≤ _N_ ≤ 10<sup>5</sup>  
0 ≤ _a<sub>i</sub>_ ≤ 10<sup>10</sup> , where _i ∈ [1 .. N]_  

**Sample Input**  

	3
	1 1 2
    
**Sample Output**  

	44

**Explanation**  

For given list, sublist and calculations are given below  
1. {1} and 2<sup>1</sup> = 2  
2. {1} and 2<sup>1</sup> = 2  
3. {2} and 2<sup>2</sup> = 4  
4. {1,1} and 2<sup>2</sup> = 4  
5. {1,2} and 2<sup>3</sup> = 8  
6. {1,2} and 2<sup>3</sup> = 8  
7. {1,1,2} and 2<sup>4</sup> = 16  
So total sum will be 44.

Cod sursa

import sys

MOD = 1000000007

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    n = int(data[0])
    arr = list(map(int, data[1:1 + n]))

    ans = 1
    for x in arr:
        ans = (ans * (1 + pow(2, x, MOD))) % MOD

    ans = (ans - 1) % MOD
    print(ans)

if __name__ == '__main__':
    main()