2022-03-23：在k进制下，最小多小的num，可以让1~num范围的数拥有1的个数不少于n个？ 腾讯音乐2022校园招聘。

2022-03-23：在k进制下，最小多小的num，可以让1~num范围的数拥有1的个数不少于n个？
腾讯音乐2022校园招聘。

答案2022-03-23：

二分法。

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

package main

import "fmt"

func main() {

	ret := minM(5, 2)

	fmt.Println(ret)

}

func minM(n, k int) int {

	len0 := bits(n, k)

	l := 1

	r := power(k, len0+1)

	ans := r

	for l <= r {

		m := l + ((r - l) >> 1)

		if ones(m, k) >= n {

			ans = m

			r = m - 1

		} else {

			l = m + 1

		}

	}

	return ans

}

func bits(num, k int) int {

	len0 := 0

	for num != 0 {

		len0++

		num /= k

	}

	return len0

}

func power(base, power int) int {

	ans := 1

	for power != 0 {

		if (power & 1) != 0 {

			ans *= base

		}

		base *= base

		power >>= 1

	}

	return ans

}

func ones(num, k int) int {

	len0 := bits(num, k)

	if len0 <= 1 {

		return len0

	}

	offset := power(k, len0-1)

	first := num / offset

	curOne := num%offset + 1

	if first != 1 {

		curOne = offset

	}

	restOne := first * (len0 - 1) * (offset / k)

	return curOne + restOne + ones(num%offset, k)

}

执行结果如下：

左神java代码

2022-03-23：在k进制下，最小多小的num，可以让1~num范围的数拥有1的个数不少于n个？ 腾讯音乐2022校园招聘。的相关教程结束。