首页 > 试题广场 >

小明的集合

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



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


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

其中  的表示方法如下：





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


示例1

输入

6

输出

3
示例2

输入

10

输出

4
算法知识视频讲解
添加回答
只想搞钱的王老五很爱吃烤肠头像 只想搞钱的王老五很爱吃烤肠 
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)
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 {
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条回答 4578浏览

热门推荐

通过挑战的用户

相关试题

小明的集合

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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