In this post, we will solve HackerRank Summing Pieces Problem Solution.
Consider an array, A. of length n. We can split A into contiguous segments called pieces and store them as another array, B. For example, if A = [1, 2, 3], we have the following arrays of pieces:
B = [(1), (2), (3)] contains three 1-element pieces.
- B= [(1,2), (3)] contains two pieces, one having 2 elements and the other having 1
element. - B= [(1), (2, 3)] contains two pieces, one having 1 element and the other having 2 elements.
- B= [(1,2,3)] contains one 3-element piece.
We consider the value of a piece in some array B to be
(sum of all numbers in the piece) (length of piece), and we consider the total value of some array B to be the sum of the values for all pieces in that B. For example, the total value of B = [(1,2,4), (5, 1), (2)] is (1+2+4) × 3+ (5+1) x 2 + (2) × 1 = 35. Given A. find the total values for all possible B’s, sum them together, and print this sum
modulo (10 power 9 +7) on a new line.

Sample Input 0
3
1 3 6
Sample Output 0
73

Sample Input 1
5
4 2 9 10 1
Sample Output 1
971

Summing Pieces C Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
typedef long long int LL;
#define din(n) scanf("%d",&n)
#define dout(n) printf("%d\n",n)
#define llin(n) scanf("%lld",&n)
#define llout(n) printf("%lld\n",n)
#define strin(n) scanf(" %s",n)
#define strout(n) printf("%s\n",n)
int arr[1000005];
int dp[1000005];
int m = 1e9 + 7;
int mod=1e9+7;
int mult(int a,int b)
{
LL tmp = (LL)a*(LL)b ;
tmp = tmp%m;
return (int)tmp;
}
int add(int a, int b)
{
LL tmp = (LL)a + (LL)b;
tmp = tmp%m;
return (int)tmp;
}
int max(int a, int b)
{
if(a>b) return a; return b;
}
long long po(int x, int y)
{
int pro=1;
while(y>0)
{
if(mod==1)
return(0);
else if(y&1 != 0)
pro = mult(pro, x);
x = mult(x,x);
y=y>>1;
}
return pro;
}
int main()
{
int n; din(n);
for(int i=0;i<n;i++)
{
din(arr[i]);
}
dp[0] = po(2,n) - 1;
dp[n-1] = po(2,n) - 1;
int len1 = n-2, len2 = 0;
for(int i=1;i<=n/2;i++)
{
dp[i] = add(dp[i-1], (po(2, len1--)-po(2,len2++))%m ); // mod
dp[n-i-1] = dp[i];
}
int ans = 0;
for(int i=0;i<n;i++)
{
//printf("%d ", dp[i]);
ans = add(ans, mult(arr[i], dp[i]));
}
//printf("\n");
dout(ans);
return(0);
}
Summing Pieces C++ Solution
#pragma region Header
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <cstdlib>
#include <stdio.h>
#include <ctime>
#include <stack>
#include <sstream>
#include <iostream>
#include <functional>
#define db(x) cerr<<#x<<"="<<(x)<<"\n"
#define X first
#define Y second
#define Z third
#define mp make_pair
#define mt make_triple
#define gch() getchar()
#define er read
#define fid(n) for (int i = (n)-1;i>=0;i--)
#define fjd(n) for (int j = (n)-1;j>=0;j--)
#define fkd(n) for (int k = (n)-1;k>=0;k--)
#define fid1(n) for (int i = (n)-1;i>=1;i--)
#define fjd1(n) for (int j = (n)-1;j>=1;j--)
#define fkd1(n) for (int k = (n)-1;k>=1;k--)
#define fi(n) for (int i = 0;i<(n);i++)
#define fj(n) for (int j = 0;j<(n);j++)
#define fk(n) for (int k = 0;k<(n);k++)
#define fi1(n) for (int i = 1;i<(n);i++)
#define fj1(n) for (int j = 1;j<(n);j++)
#define fk1(n) for (int k = 1;k<(n);k++)
#define finc(a,b,c) for (int a = b; a < c; a++)
#define fdec(a,b,c) for (int a = b; a >= c; a--)
#define tbreak if (time_break()) break;
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
//typedef pair<int, int> pii;
using namespace std;
const ll linf = 10000000000000043;
const int inf = 1000000043;
void pause(bool a = true) {
#ifdef _DEBUG
cout << "PAUSE" << endl;
string s; cin >> s;
#endif
}
template<class T>inline const T sqr(const T & x) { return x*x; }
template<class T>inline T dist(pair<T, T> a, pair<T, T> b) { return sqrt(sqr(a.X - b.X) + sqr(a.Y - b.Y)); }
template<class T>inline T prod(pair<T, T> a, pair<T, T> b, pair<T, T> c = mp(0, 0)) { return (a.X - c.X)*(b.Y - c.Y) - (a.Y - c.Y)*(b.X - c.X); }
template<class T>inline T prodv(pair<T, T> a, pair<T, T> b, pair<T, T> c = mp(0, 0)) { return (a.X - c.X)*(b.X - c.X) + (a.Y - c.Y)*(b.Y - c.Y); }
template<class T>inline bool intriangle(pair<T, T> a, pair<T, T> b, pair<T, T> c, pair<T, T> d) { return (abs(prod(a, b, c)) == abs(prod(a, b, d)) + abs(prod(a, c, d)) + abs(prod(b, c, d))); }
template<class T> inline int sg(T a) { return (a < 0 ? -1 : a ? 1 : 0); }
ll rng(ll a, ll b) { return(((((ll)rand()) << 16) + rand()) % (b - a + 1)) + a; }
bool inConvPoly(const vector<pair<ll, ll> > & a, pair<ll, ll> b)
{
ll l = 1; ll r = a.size() - 1;
if (sg(prod(a[l], b, a[0]))*sg(prod(a[r], b, a[0])) >= 0) return false; if (intriangle(a[l], a[r], a[0], b)) return true;
while (l != r - 1) (prod(a[(l + r) / 2], b, a[0]) < 0) ? l = (l + r) / 2 : r = (l + r) / 2; return sg(prod(b, a[r], a[l]))*sg(prod(b, a[0], a[l])) < 0;
}
template<class T> T mex(vector<T> a) { set<T> b(a.begin(), a.end()); for (int i = 0;; ++i)if (!b.count(i))return i; }
ll gcd(ll a, ll b) { while (b) { a %= b; swap(a, b); }return a; }
ll lcm(ll a, ll b) { return a*b / gcd(a, b); }
ll popcnt(ll mask) { ll cnt = 0; while (mask) cnt += mask % 2, mask /= 2; return cnt; }
ull powi(ull a, ull b, ll mod = 1000000007) { if (b < 2) return b ? a : 1; return (powi((a*a) % mod, b / 2, mod)*(b % 2 ? a : 1LL)) % mod; }
bool isn(char c) { return ('0' <= c && c <= '9'); }
template<class T> bool read(T &out) { int c = gch(), sign = 1; T num = 0; for (; !isn(c) && c != '-'; c = gch())if (c == EOF)return false; if (c == '-') { sign = -1; c = gch(); }if (c == EOF)return false; for (; isn(c); c = gch())num = num * 10 + c - '0'; out = sign*num; return true; }
ll time_limit = 1000000;//1sec
ll start = clock(); bool time_break() { int g = clock(); return (clock() - start > time_limit*0.9); }
ll fact(ll n, ll mod = linf) { ll g = 1; fi(n) g *= (i + 1); return g; }
void init(ll tl = 1000000) { ios::sync_with_stdio(false); srand(time(0)); time_limit = tl; }
template<class T> bool maxz(T & a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool minz(T & a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool maxze(T & a, T b) { if (a <= b) { a = b; return true; } return false; }
template<class T> bool minze(T & a, T b) { if (a >= b) { a = b; return true; } return false; }
ll mod7 = 1000000007; ll mod9 = 1000000009;
bool isprime(ll n) { if (n < 2) return 0; for (ll i = 2; i*i <= n; i++) if (n%i == 0) return 0; return 1; }
ll randLL() { return (((ll)rand()) << 47) + (((ll)rand()) << 31) + (((ll)rand()) << 15) + (((ll)rand()) >> 1); }
bool isprimeL(ll n, int it = 50) { if (n < 2) return 0; if (n == 2) return 1; if (n % 2 == 0) return 0; fi(it) { ll x = randLL() % (n - 1) + 1; if (gcd(x, n) != 1)return 0; if (powi(x, n - 1, n) != 1)return 0; }return 1; }
#pragma endregion
string gen(char a, char b, string s)
{
string t = "";
for (char c : s)if (c == a || c == b) t += c;
return t;
}
bool check(string t)
{
int l = t.length();
return (l >= 2 && t.substr(0, l - 2) == t.substr(2, l) && t[0] != t[1]);
}
ll get(vector<ll> a, vector<ll> d, vector<ll> p)
{
ll n = a.size();
ll ans = 0;
ll g = d[1];
for (int i = 0; i < n; i++)
{
ans = (ans + g*a[i]) % mod7;
g -= powi(2,n-i-1,mod7);
}
return ans;
}
ll get(ll n, ll p)
{
ll ans = 0;
fi((1 << (n - 1)))
{
int len = 1;
ll totlen = 1;
ll m = (1 << (n - 1)) + i;
bool up = false;
for (int j = 0; j < n; j++)
{
if ((m >> (n-j-1)) & 1)
{
len = 1;
if (up) break;
}
else len++;
if (j == p) up = true;
if (up) totlen=len;
}
ans += totlen;
}
return ans;
}
ll pr(ll x)
{
return (powi(2, x - 1, mod7) * 3 - 1) % mod7;
}
ll get2(ll n, ll p)
{
ll d = pr(p+1);
return (d*powi(2, n - p - 1, mod7) - powi(2, p, mod7) + mod7) % mod7;
}
int main() {
ios::sync_with_stdio(false);
#ifdef _DEBUG
ifstream cin; cin.open("test.txt");
#endif
ll n; cin >> n;
ll ans = 0;
fi(n){
ll x; cin >> x;
ans = (ans + x*get2(n, i)) % mod7;
}
ans = (ans + mod7)%mod7;
cout << ans << endl;
pause(1); return 0;
}
Summing Pieces C Sharp Solution
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;
class Result
{
/*
* Complete the 'summingPieces' function below.
*
* The function is expected to return an INTEGER.
* The function accepts INTEGER_ARRAY arr as parameter.
*/
public static int summingPieces(List<int> arr)
{
var result = 0;
var m = 1000000007;
var n = arr.Count;
var odd = n % 2;
var even = 1 - odd;
var pow2 = new int[n];
pow2[0] = 1;
for (var i = 1; i < n; ++i) {
pow2[i] = 2 * pow2[i - 1] % m;
}
var t = 0;
for (int i = 0, j = n - 1; i < n - 1; ++i, j -= 2) {
t = (int)(((long)t + arr[i] + arr[i + j]) % m);
result = (int)((result + ((long)t * (i + 1) % m) * pow2[n - 2 - i]) % m);
}
var total = (int)(arr.Select(x => (long)x).Sum() % m);
result = (int)((result + (long)total * n) % m);
if (n <= 2) {
return result;
}
t = 0;
var t2 = SafeMod(total - arr[0] - arr[^1], m);
for (var i = 0; i < n - 2; ++i) {
t = SafeMod(t + t2, m);
t2 = SafeMod(t2 - arr[i + 1] - arr[n - 2 - i], m);
result = (int)((result + ((long)t * (i + 1) % m) * pow2[n - 3 - i]) % m);
}
return result;
}
private static int SafeMod(int n, int m) {
return (int)((n % m + m) % m);
}
}
class Solution
{
public static void Main(string[] args)
{
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
int arrCount = Convert.ToInt32(Console.ReadLine().Trim());
List<int> arr = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(arrTemp => Convert.ToInt32(arrTemp)).ToList();
int result = Result.summingPieces(arr);
textWriter.WriteLine(result);
textWriter.Flush();
textWriter.Close();
}
}
Summing Pieces Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'summingPieces' function below.
*
* The function is expected to return an INTEGER.
* The function accepts INTEGER_ARRAY arr as parameter.
*/
private static final long D = 1000000007;
private static long sumPiecesR2(int [] arr) {
long sum1, sum2;
BigInteger bigD = BigInteger.valueOf(D);
int n = arr.length;
int i = 0;
sum1 = (BigInteger.TWO.modPow(BigInteger.valueOf(n), bigD).subtract(BigInteger.ONE)).mod(bigD).longValue();
sum2 = ((sum1*arr[0])%D + (sum1 * arr[n-1])%D)%D;
for(i=1; i<n-1; i++) {
if (n%2!=0 && i>n/2) {
sum1 -=(BigInteger.TWO.modPow(BigInteger.valueOf(Math.max(n-i-1, i-1)), bigD).subtract(BigInteger.TWO.modPow(BigInteger.valueOf(Math.min(i-1, n-i-1)), bigD))).mod(bigD).longValue();
}
else if (n%2==0 && i>=n/2) {
if (i == n/2) {
}
else {
sum1 -= (BigInteger.TWO.modPow(BigInteger.valueOf(Math.max(n-i-1, i-1)), bigD).subtract(BigInteger.TWO.modPow(BigInteger.valueOf(Math.min(i-1, n-1-i)), bigD))).mod(bigD).longValue();
}
}
else {
sum1 +=(BigInteger.TWO.modPow(BigInteger.valueOf(Math.max((n-i-1), i)), bigD).subtract(BigInteger.TWO.modPow(BigInteger.valueOf(Math.min(i-1, n-i-2)), bigD))).mod(bigD).longValue();
}
sum2 += ((sum1%D)*arr[i])%D;
}
return (long)(sum2);
}
public static int summingPieces(List<Integer> arr) {
int [] array = new int[arr.size()];
for(int i=0; i<arr.size(); i++)
array[i] = arr.get(i);
long res = sumPiecesR2(array);
return (int)(res%D);
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int arrCount = Integer.parseInt(bufferedReader.readLine().trim());
List<Integer> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());
int result = Result.summingPieces(arr);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}
Summing Pieces JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the summingPieces function below.
*/
function summingPieces(arr) {
const MOD = 1e9 + 7;
const n = arr.length;
function add(a, b) {
return (a + b) % MOD;
}
function sub(a, b) {
return (a - (b % MOD) + MOD) % MOD;
}
function mul(a, b) {
return Number((BigInt(a) * BigInt(b)) % BigInt(MOD));
}
const powers = [1];
for (let i = 1; i <= n; i += 1) {
powers.push(mul(powers[i - 1], 2));
}
let count = powers[n] - 1;
let pow1 = n - 2;
let pow2 = 0;
let sum = mul(count, arr[0]);
for (let i = 1; i < n; i += 1) {
const item = arr[i];
if (i < n / 2) {
count = add(count, sub(powers[pow1], powers[pow2]));
} else if (i > n / 2) {
count = sub(count, sub(powers[pow1], powers[pow2]));
}
sum = add(sum, mul(item, count));
if (i < n / 2 - 1) {
pow1 -= 1;
pow2 += 1;
} else if (i > n / 2) {
pow1 += 1;
pow2 -= 1;
}
};
return sum;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const arrCount = parseInt(readLine(), 10);
const arr = readLine().split(' ').map(arrTemp => parseInt(arrTemp, 10));
let result = summingPieces(arr);
ws.write(result + "\n");
ws.end();
}
Summing Pieces Python Solution
import sys
def sumcalc(iput,n):
coeff = []
multi = []
temp = pow(2,n,1000000007) - 1
coeff.append(temp)
if (n%2) == 0 :
k = n/2
k = int(k)
else:
k = (n + 1) / 2
k = int(k)
for j in range(1,k+1):
nxtval = (coeff[j-1] + pow(2,(n-2)-(j-1),1000000007) - pow(2,j-1,1000000007)) % ((pow(10,9) + 7 ))
coeff.append(nxtval)
nxtval = 0
multi = []
diff = n-1
for l in range(0,k):
tem = (iput[l] * coeff[l]) % (pow(10,9) + 7 )
multi.append(tem)
if diff > l:
tem = (iput[diff] * coeff[l]) % (pow(10,9) + 7 )
multi.append(tem)
diff = diff - 1
finval = sum(multi) % (pow(10,9) + 7 )
print(finval)
def main():
lth = int(sys.stdin.readline())
tm = input()
iput = []
t_iput = tm.split()
iput = [int(l) for l in t_iput]
sumcalc(iput,lth)
if __name__ == "__main__" :
main()