给定一个十进制正整数n(1≤n≤10000),写下从1到n的所有整数,然后数一下其中出现的数字“1”的个数。 例如当n=2时,写下1,2。这样只出现了1个“1”;当n=12时,写下1,2,3,4,5,6,7,8,9,10,11,12。这样出现了5个“1”。
时间: 2023-05-31 20:01:58 浏览: 251
解题思路:
对于一个数n,如果我们要计算其中1的个数,我们可以统计它的每一位上1的个数,然后把它们相加即可。
以n=1234为例,我们先考虑个位上1的个数,因为个位上的数字为4,所以它的个位上1的个数为1。接下来我们考虑十位上1的个数,因为十位上的数字为3,所以它的十位上1的个数为10(因为10-19中十位上都是3,所以有10个1)。同理,百位上1的个数为100(因为100-199中百位上都是1,所以有100个1),千位上1的个数为1000(因为1000-1999中千位上都是1,所以有1000个1)。最后把它们相加,1的个数为1111。
具体地,我们可以使用一个变量ans来记录1的个数。对于每一位上的数字,我们将当前位上的数字分为三部分:
1. 大于1的部分:对于当前位以上的数字,我们可以将其看作是一个n-1位的数,它可以取到的最大值为999...9,所以它们每一位上都可以取到1-9,共有9×(n-1)个1。
2. 等于1的部分:对于当前位上的数字为1的情况,它的贡献为当前位以下的数字加1,即如果当前位以下的数字为xyz,那么它可以取到的值为000...0~xyz,共有xyz+1个1。
3. 小于1的部分:对于当前位上的数字小于1的情况,它的贡献为0。
最后把它们加起来即可。
时间复杂度:O(logn)
完整代码:
相关问题
2: :数1的个数 【题目描述】 给定一个十进制正整数n(1≤n≤10000),写下从1到n的所有整数,然后数一下其中出现的数字“1”的个数。 例如当n=2时,写下1,2。这样只出现了1个“1”; 当n=12时,写下1,2,3,4,5,6
,7,8,9,10,11,12。这样出现了5个“1”。请你编写一个程序,计算出从1到n的所有整数中,数字“1”出现的个数。
【输入格式】
输入一个整数n。
【输出格式】
输出一个整数,表示从1到n的所有整数中,数字“1”出现的个数。
【样例输入】
12
【样例输出】
5
【样例说明】
从1到12的所有整数中,数字“1”出现的个数为5,分别是1,10,11,12中的“1”。
给定一个十进制正整数n (1≤n≤10^18), 计算n对应的二进制数中1的个数,例如十进制数6的二进制为:110,从左往右第1位和第2位都为1,所以1个数为2。
你好!要计算一个十进制正整数对应的二进制数中1的个数,你可以将该整数转换为二进制表示,然后统计其中1的个数。在大多数编程语言中,都提供了内置的方法来实现这一功能。
以下是一个示例的算法,用于计算一个十进制正整数对应的二进制数中1的个数:
1. 初始化一个计数器变量count为0。
2. 将给定的十进制正整数n转换为二进制表示。
3. 遍历二进制表示中的每一位:
- 如果当前位为1,则将计数器变量count加1。
- 如果当前位为0,则继续遍历下一位。
4. 返回计数器变量count的值,即为二进制数中1的个数。
请注意,不同编程语言的实现方式可能略有不同,但基本思路是相似的。你可以根据自己使用的编程语言选择相应的方法来实现这个功能。