2021-12-16：给定两个数a和b， 第1轮，把1选择给a或者b

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编写。代码如下：

代码语言：txt复制

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代码

java sum

0 人点赞