You are viewing a single comment's thread. Return to all comments →
can u plz tell me what is wrong in my approach. able to pass only 3 test cases, for 3 wrong answer, and remaining time out.
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <queue> #include <algorithm> using namespace std; int arr[1000000] = {0}; bool isPrime(int n) { if (n <= 1) return false; if (n <= 3) return true; if (n%2 == 0 || n%3 == 0) return false; for (int i=5; i*i<=n; i=i+6) if (n%i == 0 || n%(i+2) == 0) return false; return true; } int calc(int n) { //cout<<n<<endl; if(arr[n] > 0) return arr[n]; while(1) { int ptr; if(!isPrime(n)) { int x = ceil(sqrt(n)); for(int j=x; j<=n/2; j++) { if(j*j == n || n%j == 0) { ptr = j; break; } } int lmov = calc(n-1); int rmov = calc(ptr); arr[n] = min(rmov,lmov) + 1; //cout<<n<<" "<<arr[n]<<" "<<ptr<<" "<<lmov<<" "<<rmov<<endl; cout<<n<<" "<<arr[n]<<endl; return arr[n]; } else { arr[n] = calc(n-1) + 1; cout<<"else "<<n<<" "<<arr[n]<<endl; return arr[n]; } } } int main() { arr[1] = 1; arr[2] = 2; arr[3] = 3; int t; cin>>t; while(t--) { int n; cin>>n; calc(n); cout<<arr[n]<<endl; //for(int i = 0; i<100; i++) // cout<<i<<" "<<arr[i]<<endl; } return 0; }
Seems like cookies are disabled on this browser, please enable them to open this website
Down to Zero II
You are viewing a single comment's thread. Return to all comments →
can u plz tell me what is wrong in my approach. able to pass only 3 test cases, for 3 wrong answer, and remaining time out.