I’m having trouble getting rid of the timeout with the following stack and queue usage problem

  c++, queue, stack

problem is:
Given a string s consisting of the numeric characters 0 through 9. For each consecutive X substring of s of length K, its special value is computed as the value of X in the base B system modulo M.

Your task is to sum the special values ​​of all substrings of s of length K.
some test cases:
Input 1:
12212
3 3 5
output: 5
Input 2:
111101
4 2 15
output: 27
And my code:

#include<bits/stdc++.h>
using namespace std;

int cal(queue<char> q, int k){
    int res = 0;
    int run = 0;
    while(!q.empty()){
        res += (q.front() - '0') * (int)pow(k, k - run + 1);
        run++;
        q.pop();
    }
    return res;
}
int32_t main(){
    string s;  cin >> s;
    int k, b, m;    cin >> k >> b >> m;
    int res = 0;
    queue<char> q;
    for(int i = 0 ;i < s.size()+1; i++){
        if(q.size() < k && i > k)   break;
        if(q.size() == k){
            res += cal(q, b)%m;
            q.pop();
        }
        q.push(s[i]);
        
    }
    cout << res;

    return 0;
}

Source: Windows Questions C++

LEAVE A COMMENT