CodeFight遇到的Lambda Lazy Execute

2020-02-04

79
0
2020-02-19

題目出處 Arcade > Thr Core > 48 Weak Numbers

將一個正整數x的weakness定義為：有幾個正整數小於x，卻擁有比x多的因數

给定正整數n

1.求範圍[1,n]中最大的weakness為何?

2.求範圍[1,n]中有幾個數的weakness與此最大值相同?

題目的範例：
對於 n = 9，[1-9]中最大的weakness為2，故應回傳2
1: d(1) = 1, weakness(1) = 0;
2: d(2) = 2, weakness(2) = 0;
3: d(3) = 2, weakness(3) = 0;
4: d(4) = 3, weakness(4) = 0;
5: d(5) = 2, weakness(5) = 1;
6: d(6) = 4, weakness(6) = 0;
7: d(7) = 2, weakness(7) = 2;
8: d(8) = 4, weakness(8) = 0;
9: d(9) = 3, weakness(9) = 2.

寫完後第一次submit的程式碼：

int[] weakNumbers(int n) {
    // 將[1-n]的數以及其因數數量都算好，暫存在ds
    var ds = Enumerable.Range(1,n).Select(x => new{ num = x, d = d(x) });

    // 用上一步算好的ds計算weakness ( x>y 且 x因數數量<y因數數量 )
    var weakness = ds.Select(x => ds.Count(y => y.num < x.num && y.d > x.d));
    
    // 依照需求回傳答案
    int ww = weakness.Max();
    return new int[]{ ww, weakness.Count(x => x == ww) };
}

// 計算因數數量
int d(int n){
    return Enumerable.Range(1,n).Count(x => n % x == 0);
}

執行結果卻是超過時間限制，經過檢查後發現可能是因為Lazy Execute特性導致計算weakness時用的ds一直在重複計算

weakness看似O(n²)的運算實際上為O(n⁴)

修改程式加上ToArray之後就通過了

var ds = Enumerable.Range(1,n).Select(x => new{ num = x, d = d(x) }).ToArray();
var weakness = ds.Select(x => ds.Count(y => y.num < x.num && y.d > x.d)).ToArray();

https://codesignal.com/

回首頁