首页 > 试题广场 >

k进制下一的个数

[编程题]k进制下一的个数
  • 热度指数:481 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

进制下中数字出现的次数,记作。例如,因为三进制,数字出现了次。牛牛现在给你,他想知道,最小的是多少呢。请你返回的值。

示例1

输入

5,3

输出

5

说明

F(m,3)\geq 5,最小的\mathit m\text 5
示例2

输入

10,10

输出

17

说明

十进制下1\sim 9只有一个\text 1\text 10,11,12,13,14,15,16,17,一共\text 10\text 1。所以最小的\mathit m=17

备注:

二分搜索

m越大,肯定F(m,k)更有可能大于n。根据题意易知搜索空间的下界为,上界只要能够最小限度超过n就行,为,其中表示数n的位数。有了搜索边界,我们就可以进行二分搜索。
这个题用二分法的框架没有什么悬念,真正难的是如何在k进制下计算1~m中1的数量,可以先参考另外一个经典题目:二进制下“1到m中1的出现次数”,在那个算法原型下修改出k进制的版本。
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @return long长整型
     */
    public long minM (int n, int k) {
        // write code here
        int len = getBits(n, k);     // 计算n是几位数
        // k进制数的左右边界
        long left = 1;
        long right = (long)Math.pow(k, len + 1);
        // 二分法找最小的m
        long lowestM = right;
        while(left <= right){
            long m = left + ((right - left) >> 1);
            if(caculateOnes(m, k) < n){
                left = m + 1;
            }else{
                lowestM = m;
                right = m - 1;
            }
        }
        return lowestM;
    }
    
    // 计算k进制下1~m有多少个1
    private long caculateOnes(long num, int k) {
        int len = getBits(num, k);
        if(len <= 1){
            return len;
        }
        long offset = (long)Math.pow(k, len - 1);
        long first = num / offset;
        long curOne = first == 1 ? (num % offset) + 1 : offset;
        long restOne = first * (len - 1) * (offset / k);
        return curOne + restOne + caculateOnes(num % offset, k);
    }
    
    // 计算num有多少位
    private int getBits(long num, int radix) {
        int len = 0;
        while(num > 0){
            num /= radix;
            len++;
        }
        return len;
    }
}

编辑于 2022-01-05 15:56:29 回复(0)
抽象二分,问题是0-m有多少1。我用递归找的1的个数,分了两类,一类是以1为首位的,另一类是首位大于1的。中间计算了0~(k**p)-1即[0,0,...,0]到[k-1,k-1,...,k-1]共有多少个1,显然有k**p个数,每个数p个位,每个位可取0~k-1,那么取1的有k**p * p / k = p * k**(p-1)个1。除去首位可能取1以外,位数降低1,就可以递归了。
另外二分的时候,因为m=(k**p)-1容易得到有多少1,因此可以先拿来做初始端点值的选择。
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param n int整型 
# @param k int整型 
# @return long长整型
#
class Solution:
    def minM(self , n , k ):
        def find(m, k):
            if m==0: return 0
            if m < k: return 1
            # 找0-m(含) k进制有多少1
            a = []
            mm = m
            while mm:
                a.append(mm % k)
                mm //= k
            p = len(a) - 1
            t = 1
            s = [0] * (p+1)
            while t <= p:
                s[t] = k * s[t - 1] + k ** (t - 1)
                t += 1
            if a[p] == 1:
                ans = m - k ** p + 1 + s[p] + find(m - k ** p, k)
            else:
                ans = a[p] * s[p] + k ** p + find(m - a[p] * k ** p, k)
            return ans

        if n==1: return 1
        p = 1
        while p*k**(p-1)<n:
            p+=1
        st = k**(p-1)
        ed = k**p
        
        while st<ed-1:
            mid = (st+ed)>>1
            if find(mid, k)<n:
                st = mid
            else:
                ed = mid
        if find(st+1, k)>=n:
            return st+1
        else:
            return st+2

发表于 2023-08-09 01:31:31 回复(0)
最后一个用例不知道是啥,就是通不过,肯定是很奇怪的用例
发表于 2021-10-21 15:04:36 回复(0)