Summing Pieces problem solution

In this Summing Pieces problem solution, we have given an array A of length n and we can split A into contiguous segments called pieces and store them as another array B. so we need to find the total values for all possible B's and then sum them together and print on the output screen.

Problem solution in Python.

#!/bin/python3

import os
import sys

#
# Complete the summingPieces function below.
#
def summingPieces(arr):
    #
    # Write your code here.
    #
    
    partialSum = 0 # this is the sum including last element
    count, total, coeff = 1, 0, 0
    for i in range(len(arr)):
        val = arr[i]%(10**9+7)
        coeff += count
        coeff %= 10**9+7
        total *= 2
        total %= 10**9+7
        total += coeff*val + partialSum
        total %= 10**9+7
        partialSum += count*val
        partialSum %= 10**9+7
        count *= 2
        count %= 10**9+7
    
    return total
        
        

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    arr_count = int(input())

    arr = list(map(int, input().rstrip().split()))

    result = summingPieces(arr)

    fptr.write(str(result) + '\n')

    fptr.close()

{"mode":"full","isActive":false}

Problem solution in Java.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class SummingPieces {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int n = in.nextInt();
        long sum = 0;
        long[] powers2 = new long[n+1];
        powers2[0] = 1;
        for(int i=1; i<=n; i++)
            powers2[i] = (powers2[i-1] << 1) % 1000000007;
        
        for(int i=1; i<=n; i++){
            long left = ((powers2[i] - 1) * powers2[n-i]) % 1000000007;
            long right = ((powers2[1+n-i]-1) * powers2[i-1]) % 1000000007;
            long v = left + right - powers2[n-1];
            sum = (sum + (v * in.nextLong())) % 1000000007;
        }
        
        System.out.println(sum);
        
    }
}

{"mode":"full","isActive":false}

Problem solution in C++.

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<map>
#include<cmath>
#include<bitset>
#include<set>
#include<iomanip>
#include<fstream>
#include<bitset>
#include<cstring>
#include<cstdlib>

using namespace std;
long long mod = 1000000007LL;
typedef pair<long long ,long long> ll;
long long mul(long long x,long long y){
	x%=mod;
	y%=mod;
	return (x*y)%mod;
}
long long add(long long x,long long y){
	x%=mod;
	y%=mod;
	return (x+y)%mod;
}
int main(){
	int n;
	cin>>n;
	vector<long long> a(n,0LL);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	vector<long long> cnt(n+1,0LL);
	vector<long long> pre(n+1,0LL);
	long long sum = 1LL;
	cnt[0]=1LL;
	for(long long i=1;i<=n;i++){
		cnt[i]=sum;
		sum+=cnt[i];
		sum%=mod;
		pre[i]=sum;
	}
	vector<long long> dp(n+1,0LL);
	dp[1]=a[0];
	long long sumdp;
	sumdp=dp[1];
	sum=a[0];
	long long sum2 = a[0];
	long long f = 0LL;
	for(long long i =2;i<=n;i++){
		sum=add(sum,mul(pre[i-1],a[i-1]));
		sum2=add(sum2,sum);
		sum2=add(sum2,mul(f,a[i-1]));
		f=add(f,cnt[i-1]);
		sum2=add(sum2,mul(cnt[i-1],a[i-1]));
		dp[i]=add(sumdp,sum2);
		sumdp=add(sumdp,dp[i]);
	}
	cout<<dp[n]<<endl;

	return 0;
}

{"mode":"full","isActive":false}

Problem solution in C.

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#pragma warning(disable : 4996)

long long Pow[1000001];
long long mod = 1000000007;

long long summingPieces(int arr_count, int *arr) {
  Pow[0] = 1;
  for (int i = 1; i < 1000001; i++)
    Pow[i] = Pow[i - 1] * 2 % mod;

  long long *p = (long long *)malloc(sizeof(long long) * arr_count);
  p[0] = Pow[arr_count] - 1;

  long long sum = p[0] * arr[0];
 // printf("p[0] = %d\n", sum);
  for (int i = 1; i < arr_count; i++) {
    if (i < arr_count / 2 + 1)
      p[i] = (p[i - 1] + Pow[arr_count - i - 1] - Pow[i - 1]) % mod;
    else
      p[i] = p[arr_count - i - 1];

   // printf("p[%d] = %llu\n", i, p[i]);

    sum += (p[i] * arr[i]);
    sum %= mod;
  }

  return sum;
}

int main() {
  //FILE *f = fopen("input.txt", "r");
  int arr_count = 0;
  scanf("%d", &arr_count);

  int *arr = (int *)malloc(sizeof(int) * arr_count);

  for (int i = 0; i < arr_count; i++) {
    scanf("%d", &arr[i]);
  }
  //fclose(f);

  printf("%llu", summingPieces(arr_count, arr));

  getchar();
  return 0;
}

{"mode":"full","isActive":false}