educative.io

https://www.educative.io/courses/grokking-coding-interview-patterns-java/g2m3z3wzLDD

Courses
,
#1

I don’t understand below code why the “Math.abs(nums[pointer] % nums.length) == 0” could verify it is not a cycle because I think [3,3,3] is also a cycle, is it correct by the statement of the problem?

I think this part of the function isNotCycle does not correctly identify all valid cycles according to the problem statement. It’s an edge case that the current function would not handle correctly.

// A function to detect a cycle doesn’t exist

public static boolean isNotCycle(int[] nums, boolean prevDirection, int pointer) {

// Set current direction to true if current element is positive, set false otherwise.

boolean currDirection = nums[pointer] >= 0;

// If current direction and previous direction are different or moving a pointer takes back to the same value,

// then the cycle is not possible, we return true, otherwise return false.

if (prevDirection != currDirection || Math.abs(nums[pointer] % nums.length) == 0) {

return true;

}

return false;

}

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Solution: Circular Array Loop - Grokking Coding Interview Patterns in Java

#2

Hi @Jackie1,

The line “Math.abs(nums[pointer] % nums.length) == 0” is used to check if moving the pointer at the current index would take it back to the same value. It is a condition that is part of the algorithm’s attempt to detect cycles. However, the test case you’re referring to, that is, [3, 3, 3] does not meet all of the conditions mentioned in the problem statement to become a cycle, thus it returns False.

At first glance, we can definitely see a loop: moving from the value 3 at index 0, three steps forwards, we’ll come back to same index. But, this loop doesn’t follow the rules mentioned in the problem statement. A loop is not considered a loop if the length of the loop is 1.

Starting with the second element ‘3’, move three steps forward, we’ll reach ‘3’ and then again, we’ll keep looping over the same element. The same happens with the third element in the array. They all lead in to the single-element loop defined by ‘3’, but they themselves do not occur in any loop.

Due to these conditions, the given array doesn’t contain any valid loop.

Hope this clears your confusion regarding detecting a cycle. Happy learning :slight_smile:

2 Likes
#3

thanks

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Solution: Find The Duplicate Number - Grokking Coding Interview Patterns in Java

1 Like