We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#include<iostream>#include<algorithm>template<typenamefunc_t,typenamestep_t>inttortoise_hare(constfunc_t&run,step_torigin,size_tmaxcircle,size_t&circlepoint,size_t&circumference){step_ttortoise{origin};step_thare{origin};// Try to figure out the circumference if there are any circlescircumference=0;size_tharestop=1;// the next place for the hare to stop while(true){hare=run(hare);circumference+=1;if(tortoise==hare){break;}if(circumference<harestop){continue;}if(harestop>=maxcircle){return-1;}tortoise=hare;circumference=0;harestop=std::min(harestop<<1,maxcircle);}// Figures out the point where the circle starts.for(circlepoint=0,tortoise=origin;tortoise!=hare;++circlepoint){tortoise=run(tortoise);hare=run(hare);}return0;}intmain(){size_tN{0},S{0},P{0},Q{0};if(!(std::cin>>N>>S>>P>>Q)){return-1;}size_tcirclepoint{0},circumference{0};autodetect=[&P,&Q](size_tstep){return(step*P+Q)&0x7FFFFFFF;};if(tortoise_hare(detect,S,N,circlepoint,circumference)<0){std::cout<<N<<std::endl;// No circle detected}else{std::cout<<std::min(N,circlepoint+circumference)<<std::endl;// A circle was detected}return0;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Bit Array
You are viewing a single comment's thread. Return to all comments →
A implementation of Tortoise and Hare Algorithm: