Skip to content
thecscience
THECSICENCE

Learn everything about computer science

  • Home
  • Human values
  • NCERT Solutions
  • HackerRank solutions
    • HackerRank Algorithms problems solutions
    • HackerRank C solutions
    • HackerRank C++ solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
thecscience
THECSICENCE

Learn everything about computer science

HackerRank Summing Pieces Problem Solution

Yashwant Parihar, June 23, 2023August 1, 2024

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 CcppCSharpHackerrank Solutionsjavajavascriptpython

Post navigation

Previous post
Next post
  • HackerRank Dynamic Array Problem Solution
  • HackerRank 2D Array – DS Problem Solution
  • Hackerrank Array – DS Problem Solution
  • Von Neumann and Harvard Machine Architecture
  • Development of Computers
©2025 THECSICENCE | WordPress Theme by SuperbThemes