Sort by

recency

|

39 Discussions

|

  • + 0 comments

    😂 sometimes you gotta read the Editorial and keep moving. I'm just glad there are smart people out there!

  • + 1 comment
    
    

    public static long summingPieces(List arr) { long mod = 1000000007; int len = arr.size();

        // Base Cases
        if (len == 1) {
            return arr.get(0) % mod;
        }
        if (len == 2) {
            long totalVal = arr.get(0) + arr.get(1);
            totalVal += 2 * (arr.get(0) + arr.get(1));
            return totalVal % mod;
        }
    
        // Precompute powers of 2
        long[] powersOf2 = new long[len + 1];
        powersOf2[0] = 1;
        for (int i = 1; i <= len; i++) {
            powersOf2[i] = (powersOf2[i - 1] * 2) % mod;
        }
    
        // Initialization
        int pointer1 = 0;
        int pointer2 = len - 1;
        long multiplier = powersOf2[len] - 1;
    
        // Find first difference To next multipler
        int difPower1 = len - 2;
        int difPower2 = 0;
        long totalVal = 0;
        while (true) {
            int topElem = arr.get(pointer1);
            int bottomElem = arr.get(pointer2);
    
            // Calculate and update totalVal
            totalVal = (totalVal + (multiplier * topElem % mod)) % mod;
            if (pointer1 != pointer2) {
                totalVal = (totalVal + (multiplier * bottomElem % mod)) % mod;
            }
    
            if (pointer1 == pointer2 || pointer1 == pointer2 - 1) {
                break;
            }
    
            // Compute difference to next multipler, and update next multiplier
            long currentDifference = (powersOf2[difPower1] - powersOf2[difPower2] + mod) % mod;
            multiplier = (multiplier + currentDifference) % mod;
    
            // Increment difference powers and pointers
            difPower1--;
            difPower2++;
            pointer1++;
            pointer2--;
        }
    
        return totalVal % mod;
    }
    

    }

  • + 0 comments

    O(n)

    long summingPieces(vector<long> A) {
        long mod = 1000000007;
        vector<long> twoPower = { 1 };
        for (int i = 1; i <= A.size(); i++) twoPower.push_back((2 * twoPower.back()) % mod);
        vector<vector<long>> storage = {{A[0], A[0], A[0]}};
        long L = A[0], N, P, Q;
        for (int i = 1; i < A.size(); i++) {
            P = (storage[i-1][1] + twoPower[i] * A[i]) % mod;
            Q = (storage[i-1][2] + storage[i-1][1] + (twoPower[i+1] - 1) * A[i]) % mod;
            N = (L + Q) % mod;
            L = (L + N) % mod;
            storage.push_back({N, P, Q});
        }
        return storage.back()[0];
    }
    
  • + 0 comments

    Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Summing Pieces Problem Solution

  • + 0 comments
    def summingPieces(arr):
        D = 10 ** 9 + 7
        n = len(arr)
        c = (pow(2, n, D) - 1) % D
        v = (arr[0] * c) % D
        for i in range(2, n + 1):
            c = (c + pow(2, n - i, D) - pow(2, i - 2, D)) % D
            v = (v + arr[i - 1] * c) % D
        return v