等差級數缺少數字

Tue, 2019 Dec 31

給定一個不完全的等差數列總和，其中缺少一項數字。

題目給定總和界限 1 <= sum <= 10 ^ 8，並要求找出缺少值。

解法

第一個大於輸入值的等差級數總和這裡將它命名為解，並且解為n項等差數列(公差設為1)的總和，解是否為原先輸入值未缺失的總和?

考慮大於解與小於解的邊界情況。

小於解時，由於輸入皆為等差級數和缺少一項，總和永遠小於解，而答案只需要找出最小總和即可，因此取得第一個吻合條件的解。

大於解時，思考邊界情況**n+1，並且證明加上大於n的數值就會超過解**。考量一個n+1所產生的結果，若缺少n+1實際上只會是n的級數總和，而缺少小於n+1的情況，數值總和永遠大於解。

註: 如果以上描述含有邏輯瑕疵，或者有更清楚的證明方法，煩請打開一個issue 指正我的邏輯錯誤，筆者感激不盡

由於題目給定總和界限 1 <= sum <= 10 ^ 8，下界設為1即可，而上限必須透過數學下去求解。

這裡設定一個等式進行求解 $$ \frac{n(1 + n)}{2} = 100000000 $$

from sympy import *
from mpmath import *

n = symbols('n')
e1 = (1 + n) * n / 2 - 100000000 
solve(e1)
ans = solve(e1)[0].evalf()
ans

其中ans結果為14141.6356325698，取14141時無法滿足輸入的最大值，因此無條件進位取得14142，其級數和為100005153滿足輸入條件。

這裡進行驗算，確保log取出的數值大於10 ^ 8

n = 14142
s = (1 + n) * n / 2
s
mp.log10(s)

透過迭代的方式編寫二分搜尋法。

Binary Search