![[LeetCode] Concatenation of Array with Modular Arithmetic](https://res.cloudinary.com/practicaldev/image/fetch/s--awsSwOKu--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_800/https://cdn-images-1.medium.com/max/2672/1%2AqpZVI5_iXUnOIv3P-RsCYg.png)
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
