Amazon OA | Hackerrank | K-step-sum | interger overflow - need help

Question : K-step-sum

Array A of length N;
Q queries as L,R,K
Find K-step-sum array of A as B where B[i] = A[1]+F[i]
here F[i] is
F[i] = 0 if 1<=i<K
F[i] = sum (K<= j <= i) A[K floor(j/K)] otherwise

For each query , print from k-step-sum Array B , the sum from range L to R

*eg : *

N=2
Array A = [4,5]
Q = 2
query1 = [1,1,2] -> output is 4
query2 = [1,2,1] -> output is 21

here B array will be as ->
when k = 1 ; B= [8,13]
when K= 2 ; B= [4,9]

Constraints :-
1<= N <= 10^4
1<= Q <= 10^5
1<=K<=25
1<=L<=R<=N
1<= Ai <= 10^9

My soultion was as follows :-
Kstepsum() is the method to be completed

#include<vector>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;

vector<vector<long long>> preprocess(int N, vector<int> A) { //Used preprocessing for all k from 1 to 25

    vector<vector<long long>> bs;
    for (int k = 1; k <= 25; k++) { //for all K 
        int n = A.size();
        vector<long long> b(n, 0); //B array , i.e K-step-sum array
        for (int i = 0; i < n; i++) {
            if (i + 1 < k) { b[i] = 0; continue; }
            b[i] = (i - 1 >= 0 ? b[i - 1] : 0) + A[(k * ((i + 1) / k)) - 1];
        }

        for (int i = 0; i < n; i++)
            b[i] = b[i] + A[0];  //as per the formula

        /*
        cout<<"K="<<k<<"=";
        for(int i =0; i<n; i++)
        cout<<b[i]<<" ";
        cout<<"\n";
        */

        for (int i = 1; i < n; i++)
            b[i] = b[i - 1] + b[i];  //storing cummulative of array B

        bs.push_back(b);
    }

    return bs;
}


vector<long long> K_step_sum(int N, vector<int> A, int Q, vector<vector<int> > queries) {
    // Write your code here
    vector<long long> ans;
    vector<vector<long long >> bs = preprocess(N, A);//got preprocessed k-step-sum arrays for all k's
    for (int q = 0; q < Q; q++) {
        int L = queries[q][0];
        int R = queries[q][1];
        int K = queries[q][2];

        long long result = (R - 1 >= 0 ? bs[K - 1][R - 1] : 0) - (L - 2 >= 0 ? bs[K - 1][L - 2] : 0); //using cumulative sum to get the range sum;
        ans.push_back(result);
    }
    return ans;

}

int main() {
    //freopen("inputkstep.txt", "r", stdin);
    //freopen("outputkstep.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i_A = 0; i_A < N; i_A++)
    {
        cin >> A[i_A];
    }
    int Q;
    cin >> Q;
    vector<vector<int> > queries(Q, vector<int>(3));
    for (int i_queries = 0; i_queries < Q; i_queries++)
    {
        for (int j_queries = 0; j_queries < 3; j_queries++)
        {
            cin >> queries[i_queries][j_queries];
        }
    }

    vector<long long> out_;
    out_ = K_step_sum(N, A, Q, queries);
    cout << out_[0];
    for (int i_out_ = 1; i_out_ < out_.size(); i_out_++)
    {
        cout << " " << out_[i_out_];
    }
}

However, the sample test case cleared, but on largers values, B array was getting interger overflow, because of which , it stored -ve values.
But , I cannot get why it overflowed, as the max number even in cummulative array could be as much as 10^9 * 10^4 * 10^4 = 10^17 , which should fit in long long datatype.

Please if anyone solved it correctly , let me know where I am wrong.
Thanks Leetcode community!

Comments (2)