python计算非负整数中的位数

Question

我正在编写一个程序，用于计算非负整数的位数，该整数的上限为10^｛1000000｝，时间限制为12秒我已经声明了一个大小为1000000的数组，索引0,1,2…，1000000对应于10^{array index}表示的数字的位数。然而，对于接近10^｛10000｝的输入范围，我会收到"超过时间限制"。请在线查找相同的代码：

def Number(x):
a=[0]*(1000000)
for j in xrange(len(a)):
#print j
a[j]=j+1
i=0
flag=0
flagc=0
counter=0
while(i<len(a)-1):
#print x
if (10**i)==x:
print a[i]
flag=1
break
elif x>(10**i) and x<(10**(i+1)):
print a[i]
flag=1
break
i=i+1
if (i==len(a)-1 and flag==0 and x==(10**i)):
print a[i]
number=int(input())
Number(number+1)

请帮助如何处理上述的大输入值，因为接近10^10000 的输入将超过时间限制

Answer 1

OP在一条评论中表示，他的问题是他需要以字符串的形式进行数字输入，再加1，然后返回位数。

如果仅当字符串完全由9s组成时，在数字上加1将改变数字的数量。一个简单的测试可以实现这一点。如果全部为9s，则输出字符串长度加1，否则输出不变的字符串长度。

num = input()
length = len(num)
if num == '9' * length: # checks if string is all 9's
print(length + 1)
else:
print(length)

通过消除转换为int并返回的需要，我们节省了大量时间。这段代码在几分之一秒内执行。

Answer 2

在纯python中实现这一点的最简单方法是使用len(number)，其中"number"具有所需的基数。

Answer 3

对于那些说这是一个整数的评论者，这个问题中讨论的数据会溢出一个整数，并且由于这些数字的长度，它们必须在内存中表示为字符串。

Answer 4

如上所述，math.log10对于大数字不够准确。尝试while循环：

n = 10 ** 10000 - 1
count = 0
while n > 0:
n //= 10
count += 1
print(count)

输出：

10000

将n更改为10 ** 10000将按预期输出10001。

编辑：我发现了一些非常令人惊讶的东西(至少对我来说(：

len(str(n))

实际上非常快！我测试了高达10^1000000的数字，它在几秒钟内就完成了执行！