Why is the modulo operator used in this function?

Question

I was working on solving a challenge: Cycle in a Circular Array. I'd like for someone to help me understand how we know to use the modulus operator in this line of code?

next_index = (current_index + arr[current_index]) % len(arr)

Problem Description: We are given an array containing positive and negative numbers. Suppose the array contains a number ‘M’ at a particular index. Now, if ‘M’ is positive we will move forward ‘M’ indices and if ‘M’ is negative move backwards ‘M’ indices. You should assume that the array is circular which means two things:

If, while moving forward, we reach the end of the array, we will jump to the first element to continue the movement. If, while moving backward, we reach the beginning of the array, we will jump to the last element to continue the movement. Write a method to determine if the array has a cycle. The cycle should have more than one element and should follow one direction which means the cycle should not contain both forward and backward movements. Example:

Input: [1, 2, -1, 2, 2]
Output: true
Explanation: The array has a cycle among indices: 0 -> 1 -> 3 -> 0

Code:

def circular_array_loop_exists(arr):
  for i in range(len(arr)):
    is_forward = arr[i] >= 0  # if we are moving forward or not
    slow, fast = i, i

    # if slow or fast becomes '-1' this means we can't find cycle for this number
    while True:
      # move one step for slow pointer
      slow = find_next_index(arr, is_forward, slow)
      # move one step for fast pointer
      fast = find_next_index(arr, is_forward, fast)
      if (fast != -1):
        # move another step for fast pointer
        fast = find_next_index(arr, is_forward, fast)
      if slow == -1 or fast == -1 or slow == fast:
        break

    if slow != -1 and slow == fast:
      return True

  return False


def find_next_index(arr, is_forward, current_index):
  direction = arr[current_index] >= 0

  if is_forward != direction:
    return -1  # change in direction, return -1

  # ********** This is the line in question ***********
  next_index = (current_index + arr[current_index]) % len(arr)
  # ********** This is the line in question ***********

  # one element cycle, return -1
  if next_index == current_index:
    next_index = -1

  return next_index


def main():
  print(circular_array_loop_exists([1, 2, -1, 2, 2]))
  print(circular_array_loop_exists([2, 2, -1, 2]))
  print(circular_array_loop_exists([2, 1, -1, -2]))


main()

Answer 1

The modulus operator returns the remainder of a division. You can learn more about here.

In your context, this means it keeps the index within the circular array to avoid the index going out of bounds.

For example, if you have an array that has a length of 4, but your next index is 6, this code % len(arr) changes the 6 to become 2 because 6 % 4 = 2. So it means, it wraps the index around to the start of the array.

If your next index is 2, since 2 is less than 4, this operation % len(arr) will result in the remainder, which is 2. So the index remains unchanged if it's within the bounds of the array.

I hope that helps!

Answer 2

The modulo-operator returns the remainder of the given division. Let's say that we have the following bit of code:

>>> lst = [i for i in range(5)]
>>> lst
[0, 1, 2, 3, 4]

If we try to call an index outside of the list, we get an error:

>>> lst[5]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: list index out of range

Because the modulo-operator returns the remainder though we can do something like this instead:

>>> lst[5 % len(lst)]
0

This is because the remainder of 5 / 5 is 0. If we instead try with 6 we get the following result:

>>> lst[6 % len(lst)]
1

Once again, it's because the remainder if 6 / 5 is 1.