2221. Find Triangular Sum of an Array

Leetcode link

题目简介

题目给我们一个数组 nums ，nums 的每一个元素都是 0～9 的数字

题目要求我们按照如下步骤计算数组直到数组长度为 1 并返回唯一的元素：

1. 假设原数组有 n 个元素，创建一个长度为 n - 1 的数组 newArr
2. 对于每一个符合条件 0 <= i < n - 1 的 i，newArr[i] = (nums[i] + nums[i + 1]) % 10
3. 使用 newArr 取代原来的数组
4. 回到步骤 1

解题思路

这题有两个思路，第一个思路是直接按照题目要求模拟出来就好，复杂度是 O(n^2)，但是可以 accept

另外有一个解法用到了组合数以及中国余数定理，能够把复杂度降到 O(n)

Javascript:O(n^2)

/**
 * @param {number[]} nums
 * @return {number}
 */
var triangularSum = function(nums) {
    let res = [...nums]
    let temp = []
    let i = 0

    while(i < res.length) {
        if(res.length === 1) {
            return res[0]
        }
        if(i === res.length - 1) {
            res = temp
            temp = []
            i = 0
            continue
        }
        const nextItem = (res[i] + res[i+1]) % 10
        temp.push(nextItem)
        i++
    }

};

Javascript: O(n)

/**
 * @param {number[]} nums
 * @return {number}
 */
var triangularSum = function(nums) {
  const n = nums.length;
  if (n === 1) return nums[0] % 10;
  const m = n - 1;

  // --- mod 2 ---
  let S2 = 0;
  for (let i = 0; i <= m; i++) {
    // C(m, i) is odd iff (i & ~m) === 0
    if ((i & ~m) === 0) S2 ^= (nums[i] & 1);
  }

  // --- mod 5 ---
  const inv5 = [0, 1, 3, 2, 4]; // inverses mod 5 for 0..4 (0 unused)
  let S5 = 0;
  let e5 = 0;     // exponent of 5 in C(m, i)
  let r5 = 1;     // 5-free part of C(m, i) modulo 5

  for (let i = 0; i <= m; i++) {
    let c5;
    if (i === 0) {
      c5 = 1; // C(m,0)=1
    } else {
      // Update from C(m, i-1) to C(m, i) by * (m-i+1)/i
      let a = m - (i - 1);
      while (a % 5 === 0) { a /= 5; e5++; }
      let b = i;
      while (b % 5 === 0) { b /= 5; e5--; }

      r5 = (r5 * (a % 5)) % 5;
      r5 = (r5 * inv5[b % 5]) % 5;

      c5 = e5 > 0 ? 0 : r5; // if any factor 5 remains, coeff ≡ 0 (mod 5)
    }
    S5 = (S5 + (nums[i] % 5) * (i === 0 ? 1 : c5)) % 5;
  }

  // --- CRT combine to mod 10 ---
  const t = (S2 - (S5 & 1) + 2) & 1; // choose t in {0,1} s.t. parity matches
  return (5 * t + S5) % 10;
};