Modulo operation and circular array

Modulo is the operation that returns the remainder of one number divided by another. It is a arithmetical operator, represented as %. For example, 6 % 4 is 2. Additionally, it can by used in data structures such as circular array and circular queue. By applying it to array index, an array can be turned into a circular array. Circular queue is usually implemented with circular array. The difference is the data access is at the two ends, not by index. Here are two examples of modulo operator.


1. FizzBuzz

A simple example using modulo operation is Fizzbuzz question.

Question:
Write a program that outputs the string representation of numbers from 1 to n. For a number is multiples of three, it should output “Fizz”. For a number is the multiples of five, outputs “Buzz”. For numbers which are multiples of both three and five, outputs “FizzBuzz”.

Java

JavaScript

Python

Output:

O Notation:
Time complexity: O(1)
Space complexity: O(1)


2. Round Robin Tournament Scheduler

Here is an example of using modulo operation in circular array – Round Robin Tournament Scheduler. If there are n competitors in tournament. Each competitor meets all others in turn. The details about how it works can be found in wiki. The basis of the algorithm is using circle method. We exclude the first competitor and make all other competitors to form a circle. after each round, the competitors in the circle move forward in 1 spot and compete with different ones.

Here we apply modulo operation to implement scheduling algorithm. We put all competitors except the first one in a circular array. The index of two competitor are Nth vs. Nth-from-the-last. For the first competitor, it is index 0 vs. roundNumber%circularSize. Please note, If there are odd number of competitors, a dummy competitor can be added to make total number of teams even. Whoever scheduled to play with “dummy” shall skip in this round.


round robin scheduler

Question:
There are 10 soccer teams that will play in the league. Read the names of the teams and develop a round-robin schedule so that every team plays with every other team over the next 9 weeks.

Java

JavaScript

Python

Doodle

round robin scheduler

Output:

O Notation:
Time complexity: O(n^2)
Space complexity: O(1)
n is number of teams


Download RoundRobinScheduler.java
Download RoundRobinScheduler.js
Download RoundRobinScheduler.py
Round Robin Tournament (GitHub)

Comments are closed