Buying Sweets

Sachin likes sweets a lot. So, he goes to a market of sweets. There is a row of sweet stalls. Every sweet stall has different sweets. To save some time, he decided to buy sweets from contiguous stalls. So, he can buy from as many stalls as he wants, but all of those stalls need to be contiguous. He also decided to buy only 1 kg of sweets from each of those stalls. Cost of 1 kg of sweets for each stall is given. There is a strange rule of billing in that market. And that rule is as follows- Total cost of all sweets bought is sum of the cost of all sweets multiplied by the cost of sweet he bought at the end. e.g. if he buys sweets having cost 2, 3, 4 in the same order than total cost of sweets will be 24+34+4*4=36. Now he wonders what will be the total cost of all possible ways of buying sweets. Can you help him. Because this number could be large, you should take modulo of the final result by 10^9+7.

INPUT SPECIFICATION
Your function contains a single argument- A One dimensional Integer array of Size N in which ith element denotes the cost of 1 kg sweets from ith stall.
First line of input contains an Integer N denoting the size of Array. (1<=N<=10^5)
Next N lines of input each containing a single integer from 1 to 9.

OUTPUT SPECIFICATION
You must return an integer- sum of the cost of all possible ways of buying sweets modulo 10^9+7.

EXAMPLES
Sample Test Case 1-
Input
3
1
2
3

Output
53

Explanation
Possible ways of buying sweets are-
a) 1
b) 1 2
c) 2
d) 1 2 3
e) 2 3
f) 3
cost of each of these is following-
a) 11= 1
b) 1
2+22= 6
c) 2
2= 4
d) 13+23+33= 18
e) 2
3+33= 15
f) 3
3= 9

Hence total cost will be 1+6+4+18+15+9=53

Hi,
Basically for this question you need to find the array subsets(excluding null set) and then multiply each subset with the last ith position(of the subset), which is the price.

Note:Discard(or Don’t Create) subsets which are not continuous.
For finding array subsets refer this: http://www.geeksforgeeks.org/power-set/

Hope it helps!

can u provide answer?

Nope.
Actually I am having trouble in generating subsets of an array containing n elements. Suppose n=5 we have to generate 00000,00001,00010,00011…11111.Thereafter, we have to discard elements which are non contiguous.
It can be done in C# easily because, dynamic creation of n arrays is possible(as we know that the sequence 00000,00001,…11111 has a pattern).Though the idea is correct.

can any one help me with the code?

i have try to implement this code but i am unable to do this code. please help me to solve this question*

Can be done in O(n). Let say u have [a,b,c] as the array, expanding for the answer we get --> a^2 + 2* b^2 + 3 * c^2 + ab + ac + 2bc. So there is a pattern here.
Lets go general. Let the array be [a,b,c,d,…]. On expansion we get

a^2 + 2* b^2 + 3 * c^2 + … + a[b+c+d+…] + 2b[c+d+…] + 3c[d+e+f…] + …

so if we maintain a reverse running sum array, we will be able to get the solution in O(n).

On expanding I meant get the total sum as asked in the qs.

1 Like

can anyone explain me about possible way of buying sweets?
please , I’m not getting it.

1 Like