2021-12-16：给定两个数a和b， 第1轮，把1选择给a或者b， 第2轮，把2选择给a或者b， ... 第i轮，把i选择给a或者b。 想让a和b的值一样大，请问至少需要多少轮？ 来自字节跳动。

答案2021-12-16：

这道题很难想。 求差s。a=(sum+s)/2,b=(sum-s)/2。sum=1+2+……+i。i用倍增法。 时间复杂度：O(logN)。 空间复杂度：O(1)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    a := 19019
    b := 8439284
    ret := minStep2(a, b)
    fmt.Println(ret)
}

func minStep2(a, b int) int {
    if a == b {
        return 0
    }
    s := a - b
    if s < 0 {
        s = -s
    }
    // 找到sum >= s, 最小的i
    begin := best(s << 1)
    for (begin*(begin+1)/2-s)%2 != 0 {
        begin++
    }
    return begin
}

func best(s2 int) int {
    L := 0
    R := 1
    for R*(R+1) < s2 {
        L = R
        R *= 2
    }
    ans := 0
    for L <= R {
        M := (L + R) / 2
        if M*(M+1) >= s2 {
            ans = M
            R = M - 1
        } else {
            L = M + 1
        }
    }
    return ans
}

执行结果如下： 图片

左神java代码