|
| 1 | +class Solution { |
| 2 | +public: |
| 3 | + void sieve(vector<bool>&prime){ |
| 4 | + prime[0]= false; |
| 5 | + prime[1] = false; |
| 6 | + for(int i=2;i<10000;i++){ |
| 7 | + if(prime[i]==true){ |
| 8 | + for(int j=i*i;j<10000;j+=i){ |
| 9 | + prime[j] = false; |
| 10 | + } |
| 11 | + } |
| 12 | + } |
| 13 | + } |
| 14 | + int minOperations(int n, int m) { |
| 15 | + vector<bool>prime(10000,true); |
| 16 | + sieve(prime); |
| 17 | + if(prime[n] || prime[m]) return -1; |
| 18 | + vector<int>temp(10000,INT_MAX); |
| 19 | + priority_queue<pair< int, int>,vector<pair< int, int>>,greater<pair< int, int>>>pq; |
| 20 | + temp[n] = n; |
| 21 | + pq.push({n,n}); |
| 22 | + while(pq.size()){ |
| 23 | + auto top = pq.top(); |
| 24 | + pq.pop(); |
| 25 | + int minimum = top.first; |
| 26 | + int current = top.second; |
| 27 | + if(current ==m) return minimum; |
| 28 | + string str = to_string(current); |
| 29 | + for(int i=0;i<str.size();i++){ |
| 30 | + char c = str[i]; |
| 31 | + if(c>'0'){ |
| 32 | + str[i] = c+1; |
| 33 | + int aga = stoi(str); |
| 34 | + if(prime[aga]==false && minimum+aga<temp[aga]){ |
| 35 | + pq.push({minimum+aga,aga}); |
| 36 | + temp[aga] = minimum+aga; |
| 37 | + } |
| 38 | + } |
| 39 | + if(c<'0'){ |
| 40 | + str[i] = c-1; |
| 41 | + int aga = stoi(str); |
| 42 | + if(prime[aga]==false && minimum+aga<temp[aga]){ |
| 43 | + pq.push({minimum+aga,aga}); |
| 44 | + temp[aga] = minimum+aga; |
| 45 | + } |
| 46 | + } |
| 47 | + } |
| 48 | + str[i] = c; |
| 49 | + } |
| 50 | + } |
| 51 | + return -1; |
| 52 | + } |
| 53 | +}; |
0 commit comments