Question

杨辉三角

Answer 1

下面的图形是著名的杨辉三角形：

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯

给定一个正整数 N，请你输出数列中第一次出现 N是在第几个数？

输入一个整数 N。

输出一个整数代表答案。

示例：输入6，输出13

对于 20% 的评测用例，1≤N≤10； 对于所有评测用例，1≤N≤1000000000

最大运行时间：1s
最大运行内存: 256M

误区：一开始拿到这题，我打算用二维数组存储一个杨辉三角，后来发现测试用例数据规模很大，达到了10^9。这种时候就已经需要用long long来存储数据了。
解法描述：

3、由于每行每列对应的值都是递增的，所以如果我们想覆盖住最大的数据，也就是1e9，那么就要找到一个i，使得C2i i（组合数，懒得拍照）>1e9就可以了。
于是我们找到了这个i，便是16。这代表我们只要搜索0~32行的左半部分就可以了。
4、下面就是查找部分，因为递增的关系，要从最右边的行数查找。同时为了节省时间，运用二分查找。