3658 GCD of Odd and Even Sums

Link: https://leetcode.com/problems/gcd-of-odd-and-even-sums/description/

Đề bài#

You are given an integer n. Your task is to compute the GCD (greatest common divisor) of two values: sumOdd: the sum of the smallest n positive odd numbers. sumEven: the sum of the smallest n positive even numbers. Return the GCD of sumOdd and sumEven.

Example 1:

Input: n = 4

Output: 4

Explanation:

Sum of the first 4 odd numbers sumOdd = 1 + 3 + 5 + 7 = 16
Sum of the first 4 even numbers sumEven = 2 + 4 + 6 + 8 = 20
Hence, GCD(sumOdd, sumEven) = GCD(16, 20) = 4.

Example 2:

Input: n = 5

Output: 5

Explanation:

Sum of the first 5 odd numbers sumOdd = 1 + 3 + 5 + 7 + 9 = 25
Sum of the first 5 even numbers sumEven = 2 + 4 + 6 + 8 + 10 = 30
Hence, GCD(sumOdd, sumEven) = GCD(25, 30) = 5.

Constraints:

1 <= n <= 1000

Phân tích bài toán#

Với cách làm thông thường sẽ có 2 bước như sau:

Tính tổng n số chẵn đầu tiên, Tính tổng n số lẻ đầu tiên: Mỗi lần tính dùng 1 vòng for chạy -> n để cộng dồn
Từ 2 số thu được tìm ra ước chung lớn nhất (greatest common divisor) của chúng -> Thường sẽ dùng vòng lặp while với 2 số đã tìm được, và chia lấy phần dư rồi gán lại cho nhau (Đây gọi là Giải thuật

Phân tích: Bước số 1, time complexity là O(n), space complexity không đáng kể vì ta chỉ lưu 2 số Bước số 2, theo Định lý Lamé phát biểu rằng:

Số bước thực hiện giải thuật Euclid để tìm ước chung lớn nhất (ƯCLN) của hai số nguyên dương bất kỳ không bao giờ vượt quá (5) lần số chữ số (trong hệ thập phân) của số nhỏ hơn

Tuy nhiên với ràng buộc n max = 1000, bài toán có thể gặp vấn đề. Khi n = 1000, sumOdd lúc này sẽ là 1000000, còn sumEven sẽ là: 1001000. Có 7 chữ số => số bước tối đa phải làm có thể là: 35 bước chia và gắn lại giá trị trong vòng lặp while. Hiểu theo cách dễ dãi, 35 phép tính và 1000 bước lặp thì time-complexity vẫn nhỏ. Nhưng trong phỏng vấn thực tế, không nhiều ứng viên trả lời được tuyệt đối phân tích time complexiy, vì họ không thể nhớ được Định lý Lamé, và có thể mất thời gian tự implement lại cách tính toán theo Euclid. Dễ bị đánh fail dù làm được.

Hướng tiếp cận mới: Bản chất thì bài toán dựa trên tính chất điển hình của dãy số cộng.

1 + 3 + 5 + … + (2n-1) = n ^ 2

2 + 4 + 6 + .. + 2n = n * (n+1)

Dễ dàng tính nhanh được bước 1: time complexity O(n) -> O(1). Và theo euclid, kết quả của phép chia lấy dư lập tức xong trong 1 phép tính: bởi: (n * (n+1)) / n^2 = n => O(1). Vậy ta có lời giải: time complexity O(1), space: O(1) như bên dưới:

/** * @param {number} n * @return {number} */|
var gcdOfOddEvenSums = function(n) {
 return n;
};