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!