题解 | #杨辉三角的变形#找规律 + 大胆假设

# 看题目找规律:
# 第 5 行:             [1, 4, 10, 16, ...] 第 2 个
# 第 6 行:          [1, 5, 15, 30, ...] 第 4 个
# 第 7 行:       [1, 6, 21, ...] 第 2 个 
# 第 8 行:    [1, 7, 28, ...] 第 3 个
# 第 9 行: [1, 8, ...] 第 2 个
# ...
# 于是不同行的偶数出现的位置为:
#     [-1, -1, 2, 3, 2, 4, 2, ...]
# 我们大胆猜想, 从第 2 个开始: 
#        2, 3, 2, 4, 2, 3, 2, 4, ....
# 这样的顺序出现, 即:
#     1. 1 + 2 * n => 2; 
#     2. 4 * n => 3; 
#     3. 2 + 4 * n => 4;
# 这样的猜想是有道理的. 首先题目所给的数据范围是 [1, 10^9]
# 即便是使用 O(n) 的时间复杂度, 也肯定会超时, 
# 而看起来这题目又没有二分的方法去做, 所以肯定是找规律. 
# 代码如下:
def solution(x: int) -> int:
    if x < 3: return -1
    if x % 2 == 1: return 2
    if x % 4 == 0: return 3
    if x % 4 == 2: return 4

if __name__ == "__main__":
    n = int(input().strip())
    print(solution(n))