Problem Statement
Optimal Code
Doubt: Can anyone explain to me how this code is working practically while theoretically O(1e4*1e5) should give TLE.
Is there any mathematically reason ?
Thanks for your time.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
1 | cry | 161 |
3 | maomao90 | 160 |
4 | atcoder_official | 156 |
4 | -is-this-fft- | 156 |
6 | nor | 155 |
7 | adamant | 153 |
7 | maroonrk | 153 |
9 | Um_nik | 152 |
10 | djm03178 | 146 |
Given start, end and an array arr of n numbers. At each step, start is multiplied with any number in the array and then mod operation with 100000 is done to get the new start.
Your task is to find the minimum steps in which end can be achieved starting from start. If it is not possible to reach end, then return -1.
n<=1e4, arr[i]<=1e4, start, end<1e5
Expected Time & Space Complexity : O(1e5)
class Solution {
public:
int minimumMultiplications(vector<int>& v, int s, int d) {
int n = v.size();
int MOD = 1e5;
queue<pair<int,int>>q; q.push({s,0});
vector<int>vis(1e5); vis[s]=1;
while(!q.empty()){
auto elem = q.front(); q.pop();
int i = elem.first; int res = elem.second;
if(i==d) return res;
for(int j=0;j<n;j++){
int val = (i*v[j])%MOD;
if(!vis[val]) {
vis[val] = 1;
q.push({val,res+1});
}
}
}
return -1;
}
};
Doubt: Can anyone explain to me how this code is working practically while theoretically O(1e4*1e5) should give TLE.
Is there any mathematically reason ?
Thanks for your time.
Name |
---|
No