HackerRank Summing Pieces Problem Solution

Yashwant Parihar,

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
HackerRank Summing Pieces Problem Solution
HackerRank Summing Pieces Problem Solution

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()
c C# C++ HackerRank Solutions java javascript python