Remainder vs. Modulus

I’ve been doing HackerRank exercises lately, and came across this question. Please note that this blog post uses Java 8, so YMMV when using other languages. For those who don’t want to read a giant wall of text, below is a quick summary of the question:

You are given an array of integers, and this array is able to undergo a certain amount of “right circular rotations”. To do a rotation, you pop the last element off the array and append it to the front. So, given an array of integers, a, and an integer of the number of times the array has undergone a rotation, k, you are tasked with outputting the elements that are now at a particular set of indices (array of integers m).

For instance, if we have an array a = [1, 2, 3] and a number of rotations, k = 2, our new array will look like [2, 3, 1] since 3 got moved the front, and then 2 got moved the front. Now if we are given an array m = [0, 1, 2] containing the indices we want, we would output [2, 3, 1] since index 0 = 2, 1 = 3, and 2 = 1.

The Idea

I immediately noticed the circular pattern to this array. If you were to do one more rotation to this array (so k would be equal to 3), you would be right back where you started with [1, 2, 3]. My mind went straight to the modulus operator.

I mapped out the pattern like so:

k = 0: [A, B, (C), D] -> [A, B, (C), D] // 2 -> 2
k = 1: [A, B, (C), D] -> [D, A, (B), C] // 2 -> 1
k = 2: [A, B, (C), D] -> [C, D, (A), B] // 2 -> 0
k = 3: [A, B, (C), D] -> [B, C, (D), A] // 2 -> 3
k = 4: [A, B, (C), D] -> [A, B, (C), D] // 2 -> 2

So it seems that for every time you rotate, the desired index gets shifted once to the left. So C becomes B, B becomes A, A becomes D, D becomes C, rinse and repeat.

I came up with the following equation: newIdx = oldIdx - k % length where newIdx represents the new element index that is in the place of the old (original) index after k rotations, and length is the size of the array. Boom, all done.

The Difference

So what took me so long? For starters, I did not know exactly how the modulus operator would react to a negative number. So, I went online and tried out some modulus calculators.

Lets try this calculator from miniwebtool.com. When we input -3 % 4, we get 1. Interesting… Now lets try this other calculator from dcode.fr. If we put -3 % 4, we get -3 this time. WHAT GIVES?!

Here is the “Modulo Operation” as defined by Wikipedia:

Given two positive numbers, a (the dividend) and n (the divisor), a modulo n (abbreviated as a mod n) is the remainder of the Euclidean division of a by n. For example, the expression 5 mod 2 would evaluate to 1 because 5 divided by 2 leaves a quotient of 2 and a remainder of 1, while 9 mod 3 would evaluate to 0 because the division of 9 by 3 has a quotient of 3 and leaves a remainder of 0; there is nothing to subtract from 9 after multiplying 3 times 3.

Heres is where it gets tricky. Further down it states this:

When either a or n is negative, the naive definition breaks down and programming languages differ in how these values are defined.

Mind. Blown.

This explains why Java is giving me the undesired -3 result instead of the 1 result! Java calulates the remainder as -3 because 4 goes into -3 zero times, with a remainder of -3 (4 * 0 + -3 = -3). This is exactly how remainders work in mathematics, but I don’t want the remainder, I want the modulus!

In the table on the same wikipedia page it states that in Java, the modulo result will always have the sign of the Dividend if we use the % operator. However, if we Math.floorMod we can make the modulo result share the sign of the Divisor. So instead of -3 % 4 equaling -3, we can do Math.floorMod(-3, 4) and get 1, which will effectively help us cycle through the array backwards with no problems.

Please note that Math.floorMod is only available in Java 8. I provide an alternative solution for pre-Java 8 in my full answer below.

Here are some articles you can read to further grasp this concept:

• Mod In Java Produces Negative Numbers
• Whats the difference Between Mod and Remainder
• A Neat Trick to Compute Moduluo of Negative Numbers

Wrapping It Up

Whats makes this so interesting to me is the fact that I have been using the modulus operator for so long and have never knew that a problem like this existed. Really goes to show that there is always something new to learn.

Also here is my solution to the HackerRank problem:

static int[] circularArrayRotation(int[] a, int[] m, int k) {
    int[] values = new int[m.length];
    for (int i = 0; i < m.length; i++) {
        int idx = m[i];       
        values[i] = a[Math.floorMod(idx - k, a.length)]; // Java 8
        // Alternative solution:
        // values[i] = a[(((idx - k % a.length) + a.length) % a.length)];
    }
    return values;
}