首页 > 试题广场 >

小明的集合

[编程题]小明的集合
  • 热度指数：468 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解



给一个正整数，现在牛牛想得到一个不可重集合（该集合的元素不能重复），不重复地利用这个集合中的数进行加和可以表示出的所有数。牛牛想知道这个集合大小的最小值为多少？


例如 的时候答案为，所需要的集合为。

其中  的表示方法如下：





注意：在表示一个数时，集合中的元素不能重复使用。例如这是不符合要求的表示方法。


示例1

输入

6

输出

3
示例2

输入

10

输出

4
算法知识视频讲解
添加回答
C/C++
pein531头像 pein531
写几个可以找到规律，列举前面几个n的一个最小集合
1: {1}
2: {1,2}
3: {1,2}
4: {1,2,3}
5: {1,2,3}
6: {1,2,4}
7: {1,2,4}
8: {1,2,4,5}
9: {1,2,4,5}
10: {1,2,4,5}
11: {1,2,4,5}
12: {1,2,4,5}
13: {1,2,4,7}
14: {1,2,4,7}
15: {1,2,4,8}
……
猜测集合个数增长的规律大概是：1个1，2个2，4个3，8个4，……
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回集合大小的最小值
     * @param n long长整型 
     * @return int整型
     */
    int getSize(long long n) {
        // write code here
        long long count = 1;
        int size = 0;
        do{
            n -= count;
            count <<= 1;
            size++;
        }while(n > 0);
        return size;
    }
};
投机取巧这么就过了，但实际上我们可以通过二进制来思考这件事，只要能把n的每个位表示完就行了，需要的不重复数字个数就是n表示为二进制的长度。 
class Solution:
    def getSize(self , n ):
        return len(bin(n)) - 2

编辑于 2022-01-21 12:58:12 回复(0)
只想搞钱的王老五很爱吃烤肠头像 只想搞钱的王老五很爱吃烤肠 
class Solution:
    def getSize(self , n ):
        # write code here
        if (n==1&nbs***bsp;n==2):
            return 1
        else:
            for i in range(n):
                num = 2**i - 1
                if num>=n:
                    return i
                    break
可以发现规律，当n小于等于时，输出的结果就是k
发表于 2021-08-23 19:49:37 回复(0)
牛客151419920号头像 牛客151419920号
classSolution:
    defgetSize(self, n ):
        # write code here
        n0=bin(n)
        n1=str(n0)
        result=len(n0)-2
        returnresult
发表于 2021-08-20 15:17:59 回复(0)
轩先生头像 轩先生
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回集合大小的最小值
     * @param n long长整型
     * @return int整型
     */
    int getSize(long long n) {
        int int_mutil = 0;
        while (n / 2 != 0) {
            int_mutil++;
            n = n / 2;
        }
        //获得多少次方
        return int_mutil + 1;
    }
};

这就是个二进制问题，相当于是你把这个数字用二进制去表达了
发表于 2023-03-09 23:08:28 回复(0)
C/C++
邮你邮我头像 邮你邮我
int getSize(long long n) {
        // write code here
        int count=0;
        while(n>0)
        {
           n=n/2;
           count++;
        }
        return count;
    }
发表于 2021-08-24 20:47:14 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 大数据开发工程师 数据分析师 牛客
上传者：小小
难度：
5条回答 2538浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号