I believe the issue is that the coded algorithm is not adhering to the requirement. Specifically e1 indicates to repeat step b which fetches the next value, and **if doing this** leads to an infinite loop then print "Cycle". The problem is that the code is actually doing it, rather than checking first...
So, as the current code is written, a test case of...
12344
...will return "Done" rather than "Cyclic"...
EDIT In the parlance code, this is what I'm suggesting (untested)...
let index = 0; const seen = new Set([0]); while (true) { index = arr[index]; if (index > arr.length - 1) { console.log("Out"); break; } if (index === arr.length - 1) { console.log("Done"); break; } if (seen.has(index) || seen.has(arr[index])) { console.log("Cyclic"); break; } seen.add(index); }
EDIT #2 Upon getting a chance to test my previously untested code just above, I discovered that it did not capture the nuance of my point. So, in an effort to further clarify, below is the Current and Proposed algorithms, with sample cases to show the similarities and the difference.
The last case, where the cyclic entry is the final entry, is where step e2 reports "Cyclic" before step c is able to report "Done"...
Comments in the proposed() function show the steps of the algorithm...
function current( arr ) { let index = 0; const seen = new Set([0]); while (true) { index = arr[index]; if (index > arr.length - 1) { console.log("Out"); break; } if (index === arr.length - 1) { console.log("Done"); break; } if (seen.has(index)) { console.log("Cyclic"); break; } seen.add(index); } } function proposed( arr ) { // a. Start from index i=0; let index = 0; // b. Jump to index i=A[i]; const seen = new Set( [ index ] ); index = arr[ index ]; while( true ) { // c. If the current index i is outside the valid bound of [0..N-1], print “Out” and stop; if ( index > arr.length - 1 ) { console.log( "Out" ); break; } // d. Else if the current index i is index N-1, print “Done” and stop; if ( index === arr.length - 1 ) { console.log( "Done" ); break; } // e1. Otherwise, repeat step b; seen.add( index ); index = arr[ index ]; // e2. If doing this leads to an infinite loop, print “Cyclic” and stop; if ( seen.has( arr[index] ) ) { console.log("Cyclic"); break; } } } arr = [1,0,2]; console.log( arr ); current( arr ); proposed( arr ); arr = [1,2,3,4,5]; console.log( arr ); current( arr ); proposed( arr ); arr = [1,2,3,6,5]; console.log( arr ); current( arr ); proposed( arr ); arr=[1,2,3,4,0]; console.log( arr ); current( arr ); proposed( arr );
