HackerRank Summing Pieces Problem Solution

HackerRank Summing Pieces Problem Solution

Posted on By Yashwant Parihar No Comments on HackerRank Summing Pieces Problem Solution

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 Tags:, , , , , ,

Related Posts

HackerRank Taum and B'day Problem Solution HackerRank Taum and B’day Problem Solution c
HackerRank Insertion Sort - Part 2 Problem Solution HackerRank Insertion Sort – Part 2 Solution c
HackerRank Migratory Birds Problem Solution HackerRank Migratory Birds Problem Solution c
HackerRank Training the army Problem Solution HackerRank Training the army Problem Solution c
HackerRank Zurikela's Graph Problem Solution HackerRank Zurikela’s Graph Problem Solution c
HackerRank Number Line Jumps Problem Solution HackerRank Number Line Jumps Problem Solution c

Leave a Reply

Your email address will not be published. Required fields are marked *