2965. Find Missing and Repeated Values
https://leetcode.com/problems/find-missing-and-repeated-values/
一個n*n矩陣 填入n*n數字
但多一個a(出現兩次)少一個b(出現零次)
求[a, b]
Solution:
數學題
1.不考慮ab情況 矩陣總和是個d=1的等差數列
d=1的等差數列總和是 n^2(n^2 + 1) / 2 視為 sum0
題目矩陣多a少b所以是 sum0 + a - b = sum
2. 不考慮ab情況 矩陣平方和
d=1的等差數列平方和是 n^1(n^1 + 1)(2n^2 + 1) / 6 視為 sum_of_square0
題目矩陣多a少b所以是 sum_of_square0 + a^2 - b^2 = sum_of_square
解聯立方程式就能得到答案
聯立1: sum0 - sum = a - b
聯立2: sos - sos0 = a^2 - b^2 = (a + b)(a - b)
把1代入2: sos - sos0 = (a + b)(sum0 - sum)
化成3: (sos - sos0)/(sum0 - sum) = a + b
用1跟3相加跟相減解a,b
a = [(sos - sos0)/(sum0 - sum) + (sum0 - sum)] / 2
b = [(sos - sos0)/(sum0 - sum) - (sum0 - sum)] / 2
計算之後得解答
Code:
impl Solution {
fn find_missing_and_repeated_values(grid: Vec<Vec<i32>>) -> Vec<i32> {
let n = grid.len();
let n2 = n * n;
let expected_sum = (n2 * (n2 + 1) / 2) as i64;
let expected_sum_sq = (n2 * (n2 + 1) * (2 * n2 + 1) / 6) as i64;
let mut actual_sum: i64 = 0;
let mut actual_sum_sq: i64 = 0;
for i in 0..n {
for j in 0..n {
let val = grid[i][j] as i64;
actual_sum += val;
actual_sum_sq += val * val;
}
}
let x = actual_sum - expected_sum;
let y = (actual_sum_sq - expected_sum_sq) / x;
let a = ((x + y) / 2) as i32;
let b = ((y - x) / 2) as i32;
vec![a, b]
}
}