python count no of digits in a non negative integer

Question

I am writing a program for counting number of digits in a non negative integer whose upper bound is 10^{1000000} and has a time limit of 12 seconds I have declared an array with size 1000000 and the indexes 0,1,2...,1000000 correspond to the number of digits of the number represented by 10^{array index}. However I am getting Time Limit Exceeded for input ranges close to 10^{10000}. Please find inline the code for the same:

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)

Please help as to how to handle large input values for the above as time limit got exceeded is coming for inputs close to 10^10000

I tried the log approach but it works well for a number having 15 digits. — Sumeet ten Doeschate, Nov 27 '18 at 21:19
It looks like you're already receiving input in decimal. Why not just return the length of the decimal input string you receive? — user2357112, Nov 27 '18 at 21:20
It is slow if we are converting our input to string and then computing its length. — Sumeet ten Doeschate, Nov 27 '18 at 21:21
Your input is *already* string -- that's how the `input` function returns it. Your main code takes the time to convert it to `int`. — Prune, Nov 27 '18 at 21:23
@d_kennetz for math.log10 it is working till number having 15 digits — Sumeet ten Doeschate, Nov 27 '18 at 21:26
You need to add 1 to all log 10 values, it works with 15 digits — d_kennetz, Nov 27 '18 at 21:28
but the input in the question has a upper bound number of 1000001 digits — Sumeet ten Doeschate, Nov 27 '18 at 21:31
Yeah, this solution is mathematically sound regardless of the number of digits of the input. — iz_, Nov 27 '18 at 21:35
@d_kennetz Floats aren't precise enough with numbers this big `log10(10 ** 10000)` is equal to `log10(10 ** 10000 - 1)` even though those numbers have different numbers of digits. — Patrick Haugh, Nov 27 '18 at 21:37
try this https://stackoverflow.com/questions/16174399/overflowerror-long-int-too-large-to-convert-to-float-in-python — an_owl, Nov 27 '18 at 21:40
I see what you are saying. It would have 1 less but it is calling them as equal — d_kennetz, Nov 27 '18 at 21:40

score 0 · Answer 1 · answered Nov 27 '18 at 21:22

0

The simplest way to do this in pure python is to use len(number) where "number" has the required base.

answered Nov 27 '18 at 21:22

GiovanH

359
2
9

iz_ · Answer 2 · 2018-11-28T06:37:40.823

0

As shown above in the comments, math.log10 is not accurate enough for large numbers. Try a while loop:

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

print(count)

Output:

Changing n to 10 ** 10000 outputs 10001 as expected.

EDIT: I found something very surprising (to me, at least):

len(str(n))

is actually EXTREMELY fast! I tested for numbers up to 10^1000000, and it finishes executing in a matter of seconds!

edited Nov 28 '18 at 06:37

answered Nov 27 '18 at 21:50

iz_

15,923
3
25
40

i tried this method but when i change the value of n to 10**100000 am getting time limit exceeded – Sumeet ten Doeschate Nov 27 '18 at 22:00
I just tried with 6 zeros (your program requirement), finished with the correct result in about 8 minutes. – iz_ Nov 28 '18 at 01:09
Actually the problem has time limit as 12 seconds – Sumeet ten Doeschate Nov 28 '18 at 02:06
Well, you should have at least specified that in your question. Let's see what I can find... – iz_ Nov 28 '18 at 02:08
@SumeettenDoeschate See my edited answer, apparently the "slow" method isn't that shabby! – iz_ Nov 28 '18 at 06:38
am getting time limit exceeded for a particular test case – Sumeet ten Doeschate Nov 28 '18 at 15:57
It depends on the computer it is being run on. – iz_ Nov 28 '18 at 19:05
i am submitting the program on online judge platform there a test case is getting time limit exceeded error – Sumeet ten Doeschate Nov 28 '18 at 19:16
Could you link the website you are submitting to ? – iz_ Nov 28 '18 at 23:14
If you are taking input as a string, **it is a total waste of time to convert it into an int and back.** Please confirm that you are indeed taking an `int` as the input, as in your code you are doing `int(input())`. If you are actually taking a string, just use `len(input())` and all of your problems will be solved in one line. – iz_ Nov 29 '18 at 01:55
Actually 1 has to be added after taking the input so am converting it to int first – Sumeet ten Doeschate Nov 29 '18 at 02:04
In that case, I have a completely different approach that does not require you to convert it to an `int`. I will post in a separate answer. – iz_ Nov 29 '18 at 02:07
Thanks for the help the submission passed successfully – Sumeet ten Doeschate Nov 29 '18 at 02:44

score 0 · Answer 3 · answered Nov 28 '18 at 02:22

0

To the commenters saying that this is an integer, the data being discussed in this question would overflow an integer, and these numbers would have to be represented as a strings in memory due to their length.

answered Nov 28 '18 at 02:22

miles_b

335
3
10

In Python 3, `int`s are unbounded by size. – iz_ Nov 28 '18 at 02:28

iz_ · Accepted Answer · 2018-11-29T02:44:15.947

OP has stated in a comment that his problem is he needs to take a numerical input in the form of a string, add 1 to it, and return the number of digits.

Adding 1 to a number will change the number of digits IF AND ONLY IF the string is composed completely of 9s. A simple test can achieve this. If it is all 9s, output the string length plus 1, otherwise output the unchanged string length.

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

By eliminating the need to convert to int and back, we save a lot of time. This code executes in fractions of a second.

Thanks for the help the submission passed successfully – Sumeet ten Doeschate Nov 29 '18 at 02:44 — Sumeet ten Doeschate, Nov 29 '18 at 02:44

python count no of digits in a non negative integer

4 Answers4