[LeetCode] Concatenation of Array with Modular Arithmetic

This is a memo of when I solved 1929. Concatenation of Array.

Question

You're given an array, nums, of arbitrary length. Your task is to return a new array, ans, that is twice as long as nums. The new array, ans, should satisfy the following conditions: ans[i] == nums[i] and ans[i + n] == nums[i], where 0 ≤ i < n.

Modular Arithmetic

Modular arithmetic is a mathematical system that operates on integers by focusing on the remainder. The expression, x mod N, asks for the remainder of x when divided by N. For example, 13 mod 5 results in 3, because 3 is the remainder when 13 is divided by 3. a ≡ b (mod N) means that they share the same remainder when divided by N — for instance, 17 ≡ 8 (mod 3). In other words, modular arithmetic is a system that groups integers with their reminders.

Solution Approach

Let’s say the nums = [1, 2, 3]. The ans should be [1, 2, 3, 1, 2, 3] = [nums[0], nums[1], nums[2], nums[0], nums[1], nums[2]]. Therefore in general, we want to get an array of [nums[0], nums[1],,,, nums[nums.lenght-1], nums[0], nums[1],,,, nums[nums.lenght-1]].

Here is the time to employ modular. Let’s set i as an arbitral index of nums, N as the length of nums, and idx as an arbitral index of ans. Then we can get idx with i mod N. With the example above, 0 mod 3 = 3 mod 3 = 0, 1 mod 3 = 4 mod 3 = 1, 2 mod 3 = 5 mod 3 = 2.

Implementation

% is the operator that gets reminders in JavaScript.

    /**
     * @param {number[]} nums
     * @return {number[]}
     */
    var getConcatenation = function(nums) {
        let ans = []
        for(let i = 0; i < nums.length * 2 ; i ++){
            const idx = i % nums.length // i mod nums.length
            ans.push(nums[idx])
        }
        return ans
    };

Generalization

What I like about the solution most is that it’s easy to generalize the number of concatenations. The question asks to repeat two times, but we can easily modify the code to repeat any number of times you want.

    /**
     * @param {number[]} nums
     * @param {number} x // the number of repetition
     * @return {number[]}
     */
    var getConcatenation = function(nums, x) {
        let ans = []
        for(let i = 0; i < nums.length * x; i ++){
            const idx = i % nums.length // i mod nums.length
            ans.push(nums[idx])
        }
        return ans
    };

⚠️ This is not a recommended answer, but I just wanted to say there is a way to utilize Math. You can find a model answer here: https://youtu.be/68isPRHgcFQ

Ref

Modular Arithmetic | Brilliant Math & Science Wiki

The original article is here