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 similar to circular array except the data access is at the two ends, not by index.

Table of Content


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 multiples of three it should output “Fizz” instead of the number, and for 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 Nrd vs. Nrd from the last. For the first competitor, it is index 0 vs (round number % 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 ModuloOperatonInCircularArray.zip
Round Robin Tournament (GitHub)
circular queue implementation

Comments are closed