Modulo is the operation that returns the remainder of one number divided by another. It is a arithmetical operator, represented as % in Java. For example, 6 % 4 is 2. In this post we are not using it as math operator, instead focus on the use of modulo operation in circular array. By applying it to array index, an array can be turned into a circular array.

Here are two examples of using modulo operation in circular array . The first one is to check whether a char array has consecutive letters, such as ‘abcd’. The trick part of this question is that the letter at the end of the array circles back to the start. For example, ‘c’, ‘d’, ‘a’, b’ has consecutive letters. Because after letter ‘b’ at the index 3, will continue to index 0. The solution is to use mod operator – The index after 3 is 4, when 4 mod by array length 4, the index becomes 0.

A more complicated use is **Round Robin Tournament Scheduler**. The details about how it works can be found in wiki. The basis of the algorithm is using circle method. So we apply modulo operation to implement scheduling algorithm. Please note, If there are an odd number of competitors, a dummy competitor can be added, whose scheduled opponent in a given round does not play and has a “bye”.

I. Basic modulo operation in circular array

**Question:**

Write a method to test whether an array has four consecutive letters.

following examples are true:

{‘d’, ‘e’, ‘f’, ‘g’}

{‘z’, ‘a’, ‘b’, ‘c’} ‘z’ is followed by ‘a’

{‘x’, ‘y’, ‘z’, ‘a’}

following examples are false:

{‘a’, ‘b’, ‘k’, ‘d’}

{‘b’, ‘x’, ‘y’, ‘z’}

** Java Code:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
import java.util.*; public class FindConsectiveLetters { static boolean check(char s[]) { if (s.length<4) return false; for (int i = 0; i < s.length; i++) { boolean found = true; for (int j = (i+1); j < (i+4); j++) { int x = j; int y = j-1; if (x >= s.length) x = x % s.length; if (y >= s.length) y = y % s.length; if (s[x] - s[y] != 1 && s[x] - s[y] != -25) { found = false ; break; } } if (found == true) return true; } return false; } public static void main(String[] args){ char[] a = {'a','x','y','z'}; System.out.println(Arrays.toString(a)); boolean res = check(a); System.out.println(res); char[] b = {'z','a','b','c'}; System.out.println(Arrays.toString(b)); res = check(b); System.out.println(res); } } |

**Output:**

[a, x, y, z]

true

[z, a, b, c]

true

**O Notation:**

Time complexity: O(n*k) ~ O(n)

Space complexity: O(1)

n is array length, k is 4 (constant)

II. Round Robin Tournament

**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 Code:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
public class RoundRobinScheduler { static void scheduler(String[] teams) { int numOfTeams = teams.length; String[] evenTeams; int k = 0; if (numOfTeams % 2 == 0) { evenTeams = new String[numOfTeams-1]; for(k = 0; k < numOfTeams-1; k++) evenTeams[k] = teams[k+1]; } else { evenTeams = new String[numOfTeams]; for(k = 0; k < numOfTeams-1; k++) evenTeams[k] = teams[k+1]; evenTeams[numOfTeams-1] = "Bye"; } int teamsSize = evenTeams.length; //it is even number int total = ((teamsSize+1) - 1); // rounds needed to complete tournament int halfSize = (teamsSize+1) / 2; int count = 0; for (int week = total-1; week >= 0; week--) { System.out.println("week " + (++count)); int teamIdx = week % teamsSize; if(!evenTeams[teamIdx].equals("Bye")) System.out.println(teams[0] + " vs. "+ evenTeams[teamIdx] ); for (int i = 1; i < halfSize; i++) { int firstTeam = (week + i) % teamsSize; int secondTeam = (week + teamsSize - i) % teamsSize; if ( !evenTeams[firstTeam].equals("Bye") && !evenTeams[secondTeam].equals("Bye")) System.out.println(evenTeams[firstTeam] + " vs. "+ evenTeams[secondTeam]); } System.out.println(); } } public static void main(String[] args) { String[] teams = {"Cosmos", "Red bull", "Manchester United", "Liverpool", "Staples", "Westhill", "Giants", "Foo Fighters", "iphoners", "Attackers"}; scheduler(teams); } } |

**Output:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
week 1 Cosmos vs. Attackers Red bull vs. iphoners Manchester United vs. Foo Fighters Liverpool vs. Giants Staples vs. Westhill week 2 Cosmos vs. iphoners Attackers vs. Foo Fighters Red bull vs. Giants Manchester United vs. Westhill Liverpool vs. Staples week 3 Cosmos vs. Foo Fighters iphoners vs. Giants Attackers vs. Westhill Red bull vs. Staples Manchester United vs. Liverpool week 4 Cosmos vs. Giants Foo Fighters vs. Westhill iphoners vs. Staples Attackers vs. Liverpool Red bull vs. Manchester United week 5 Cosmos vs. Westhill Giants vs. Staples Foo Fighters vs. Liverpool iphoners vs. Manchester United Attackers vs. Red bull week 6 Cosmos vs. Staples Westhill vs. Liverpool Giants vs. Manchester United Foo Fighters vs. Red bull iphoners vs. Attackers week 7 Cosmos vs. Liverpool Staples vs. Manchester United Westhill vs. Red bull Giants vs. Attackers Foo Fighters vs. iphoners week 8 Cosmos vs. Manchester United Liverpool vs. Red bull Staples vs. Attackers Westhill vs. iphoners Giants vs. Foo Fighters week 9 Cosmos vs. Red bull Manchester United vs. Attackers Liverpool vs. iphoners Staples vs. Foo Fighters Westhill vs. Giants |

**O Notation:**

Time complexity: O(n^2)

Space complexity: O(1)

n is number of teams

Download ModuloOperatonInCircularArray.zip

Round Robin Tournament (GitHub)