Google kickstart solution In python| Alice presented her friend Bob with an array of N positive integers, indexed from 1 to N. She challenged Bob with many queries of the form "what is the sum of the numbers between these two indexes?" But Bob was able to solve the problem too easily.

GOOGLE KICKSTART SOLUTION

Problem

Alice presented her friend Bob with an array of N positive integers, indexed from 1 to N. She challenged Bob with many queries of the form "what is the sum of the numbers between these two indexes?" But Bob was able to solve the problem too easily.

Alice took her array and found all N*(N+1)/2 non-empty subarrays of it. She found the sum of each subarray, and then sorted those values (in nondecreasing order) to create a new array, indexed from 1 to N*(N+1)/2. For example, for an initial array [2, 3, 2], Alice would generate the subarrays [2], [3], [2], [2, 3], [3, 2], and [2, 3, 2] (note that [2, 2], for example, is NOT a subarray). Then she'd take the sums -- 2, 3, 2, 5, 5, 7 -- and sort them to get a new array of [2, 2, 3, 5, 5, 7].
Alice has given the initial array to Bob, along with Q queries of the form "what is the sum of the numbers from index L_i to R_i, inclusive, in the new array?" Now Bob's in trouble! Can you help him out?
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with one line with two space-separated integers N and Q, denoting the number of elements in the initial array and the number of Alice's queries. Then, there is one line with N space-separated integers, denoting the elements of Alice's initial array. Finally, there are Q more lines with two space-separated integers each: L_i and R_i, the inclusive index bounds for the i-th query.
For each test case, output one line with Case #x:, where x is the test case number (starting from 1). Then output Q more lines, each with one integer, representing the answers to the queries (in the order they were asked).
Time limit: 30 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 10.
1 ≤ Q ≤ 20.
1 ≤ each element of the initial array ≤ 100.
1 ≤ L_i ≤ R_i ≤ N*(N+1)/2.
Small dataset (Test Set 1 - Visible)
1 ≤ N ≤ 10³.
Large dataset (Test Set 2 - Hidden)
1 ≤ N ≤ 200000.

Input

Output

Limits

Testcases1:

Input:

[1.2.3]

Output:

[5,3,4,1,2,3,6]

Testcases2:

Input:

{2,3,2]

Output:

[5,5,2,3,2,7]

#Let here i will tell the first thing i.eyou must have to understand algorithm of the problem or question.

Then read the problem line by line and take pencil and paper to write whatever is given .

if  you have understood the problem and you hsve wrote in paper,then see what inputs require and what output requires.if you follow all these things then you will be able to solve and to make a program.

So in this problem

1.you have to input one list ,and then make a combination of all elements to another .but not to same like(2,2) is not needed.andthen the sum of every combination you have to print

2.as well as input list elements also

3.,and all input  element sums and make it sungle element and then print all element.

Let us understand using example:

L=[1,2,3]

answer of point 1.

i.e [1,2],[2,3],[3,1] then combinations sum i.e

[1+2],[2+3],[3+1]=

[3],[5],[4], now your three elements are ready.

then answer of point 2:

i.e

[1],[2],[3]

answer of point 3 i.e

[1+2+3]=

[6]

 

now your element of the new list i.e [3,5,4,1,2,3,6]  this is require output for this problem. 

Steps to follow:

1.First input the list using input() function and use eval() to type so that it can accept +very, -very, number. 

2.Then take two empty list so that you can add the elements of the sum of the combination and  sum of the elements of the input list. 

3.Now take for loop which will start from last index value and go to 0 index value and updating of -1 otherwise by default update always of +1. And test the condition using if -else structure because we don't have to take a sum of the  combination which are same  numbers . 

4.Then if the condition is true then add both elements and in the next take sum of both elements or combination. And then the sum of the combination add into another  empty list I. E  L2. 

5.Now take another empty list I. E L3 to add element I. E sum of the elements of the input list using sum() function. Or You can use loop to get the sum of the elements. 

6.Now you have got all required list so you just have to concatenate input list, L2 list and L3 list. 

#Let input the list using input()

lst_1=eval(input("Enter a list:"))

L_1=[ ] #we have to take two empty list to add the elements of the input list and their sum of their combinations

L_2=[ ]

Sum=0 #here sum is 0

n=len(lst)

    

 # Now take a for loop to make cobinations of two pair of elements and this loop will start from last element to go upto starting element of the list  

for i in range(n-1,-1,-1):

    if lst[i]!=lst[i-1]:

        

    

        L1.extend([lst[i],lst[i-1]])

        Sum+=lst[i]+lst[i-1]

        

        L2.append(Sum)

        Sum=0

        

L_3=[ ] 

S=sum(lst)

L_3.append(S)

print(L_2+lst_1+L_3)

How this program will run

Let take an example 

lst_1=[1,2,3]

Sum=0

n=3

First time loop will run:

i=2 

lst_1[2]!=lst_1[2-1]

3!=2

L_1=[3.,2]

Sum=Sum+L_1[i]+L_11[i-1]=0+3+2=5

L_2=[5]

Sum=0

Second time

i=1

lst_1[1]!=lst_[0]

2!=1

L_1=[2,1]

Sum=2+1=3

L_2=[5,3]

Sum=0

Now third time time loop run:

i=0

lst_1[0]!=lst_1[0-1]

1!=3       # because at -1 index 3

L_1=[1,3]

Sum=1+3=4

L_2=[5,3,4]

Now here your loop will end and then your program come out of the loop then we have assumed L_3 is empty list.In which we append the sum of the elements of the input list i.e lst_1.Then we concatenate the all three lists i.e L_1 ,L_2 and L_3.