Finding a value of an array in a circular fashion, when giving a starting index

Question

I'm hoping that someone can help with a small algorithm problem that involves finding the correct value of an array in a "circular" fashion. My example is in javascript, although in theory it could be any language.

Here is the scenario: I have an array of numbers, and a "current pointer" that is some index value of the array. I want to pass in a "diff" integer value, which might be positive or negative. If diff is negative, then the pointer index decreases, looping back to the other side of the array. If positive, then the pointer index increases, and loops back to the other side of the array if out of bounds.

I've included some sample calls below to indicate sample function calls, and the expected output.

var arr = [0, 1, 2, 3, 4];

// starting at current index, increase or
// decrease index of arr by "diff" amount
// and then return the value at that index

function getValue(arr, current, diff) {

    var newIndex;

    if ( diff >= 0 ) {
        // increase current value by diff
        // increments, in a circular fashion
    }
    else if ( diff < 0 ) {
        // decrease current value by diff
        // increments, in a circular fashion
    }

    return arr[newIndex];
}

// sample calls, with expected output

getValue(arr, 0, 2); // 2
getValue(arr, 0, 4); // 4
getValue(arr, 0, 5); // 0
getValue(arr, 0, 12); // 2
getValue(arr, 0, -1); // 4
getValue(arr, 0, -7); // 3

getValue(arr, 3, 2); // 0
getValue(arr, 3, 4); // 2
getValue(arr, 3, 5); // 3
getValue(arr, 3, 12); // 0
getValue(arr, 3, -1); // 2
getValue(arr, 3, -7); // 1

Answer 1

var arr = [0, 1, 2, 3, 4];
function getValue(arr, current, diff) {
    if (diff >=0) {
        return arr[(current+diff) % arr.length];
    }
    else {
        return arr[(arr.length + ((current+diff) % arr.length)) % arr.length];
    }
}

console.log(getValue(arr, 0, 2)); // 2
console.log(getValue(arr, 0, 4)); // 4
console.log(getValue(arr, 0, 5)); // 0
console.log(getValue(arr, 0, 12)); // 2
console.log(getValue(arr, 0, -1)); // 4
console.log(getValue(arr, 0, -7)); // 3

console.log(getValue(arr, 3, 2)); // 0
console.log(getValue(arr, 3, 4)); // 2
console.log(getValue(arr, 3, 5)); // 3
console.log(getValue(arr, 3, 12)); // 0
console.log(getValue(arr, 3, -1)); // 2
console.log(getValue(arr, 3, -7)); // 1

var arr = [0, 1, 2, 3, 4];
function getValue(arr, current, diff) {
    if (diff >=0) {
        return arr[(current+diff) % arr.length];
    }
    else {
        return arr[(arr.length + ((current+diff) % arr.length)) % arr.length];
    }
}

console.log(getValue(arr, 0, 2)); // 2
console.log(getValue(arr, 0, 4)); // 4
console.log(getValue(arr, 0, 5)); // 0
console.log(getValue(arr, 0, 12)); // 2
console.log(getValue(arr, 0, -1)); // 4
console.log(getValue(arr, 0, -7)); // 3

console.log(getValue(arr, 3, 2)); // 0
console.log(getValue(arr, 3, 4)); // 2
console.log(getValue(arr, 3, 5)); // 3
console.log(getValue(arr, 3, 12)); // 0
console.log(getValue(arr, 3, -1)); // 2
console.log(getValue(arr, 3, -7)); // 1

Answer 2

This is when the concept of modulus is important: it is basically the remainder of a division. What you want is to get the matching index of an element, regardless of how many times to iterate through the same array. This is effectively finding the modulus of array length and the number of steps (diff) you want to move:

function getValue(arr, current, diff) {

    var newIndex = (current + diff) % arr.length;

    // If the new index is negative, we just count backwards from the end of the array
    if (newIndex < 0)
      newIndex = arr.length + newIndex;

    return arr[newIndex];
}

What the logic above does is that:

1. It decides how far ahead/behind the array it should travel. We simply add up current and diff
2. Use the modulus operator, %, to determine the final index we are in after looping through the array as many times as we can until there is no remainder left
3. If the index is negative (which is possible if we travel backwards), then we simply see it as "counting backwards from the end of the array"

---

See proof-of-concept below:

var arr = [0, 1, 2, 3, 4];

function getValue(arr, current, diff) {

    var newIndex = (current + diff) % arr.length;
    
    // If the new index is negative, we just count backwards from the end of the array
    if (newIndex < 0)
      newIndex = arr.length + newIndex;
      
    console.log(newIndex);
    return arr[newIndex];
}

// sample calls, with expected output

getValue(arr, 0, 2); // 2
getValue(arr, 0, 4); // 4
getValue(arr, 0, 5); // 0
getValue(arr, 0, 12); // 2
getValue(arr, 0, -1); // 4
getValue(arr, 0, -7); // 3

getValue(arr, 3, 2); // 0
getValue(arr, 3, 4); // 2
getValue(arr, 3, 5); // 3
getValue(arr, 3, 12); // 0
getValue(arr, 3, -1); // 2
getValue(arr, 3, -7); // 1