CODEWITHSUNDEEP
python
user3982654
user3982654

Reputation:

Runtime error running a for loop

I've made this code to find all numbers that have a squareroot ie 4 = 2 from the list. I get a Runtime error when I run it on the following test case. I need to know why it's crashing because the test environment I'm using online doesn't seem to work.

import math

for line in fileinput.input():
    if type(line) == str:
        string= line.split(' ')
        if len(string) == 2:
            start,end = int(string[0]),int(string[1])
            counter = 0
            for num in range(start,end+1):
                sqrt,floor = math.sqrt(num),math.floor(math.sqrt(num))
                if sqrt == floor:
                    counter += 1

            print counter

Here's the test case

100
465868129 988379794
181510012 293922871
395151610 407596310
481403421 520201871
309804254 776824625
304742289 566848910
267554756 828997506
387224568 926504395
244571677 871603971
444567315 582147918
334350264 342469009
400474096 410940967
488907300 943628573
26441071 801576263
182001128 267557939
115732998 974318256
192538332 862327048
45429427 307805497
358658006 842644090
92930998 431601473
231163983 893672132
275221547 298953978
351237326 981399371
484598992 985428966
103405553 529324202
37393469 768655346
30179914 482808626
208821550 538302223
154654533 791652309
68424067 854065374
246956110 517538724
51395253 876949418
57778758 368742600
227566632 606529208
360551779 824396068
396042598 543511438
411041425 473345854
469310505 774761014
90386202 342472887
79110819 503433812
444288332 918848597
280603787 548642983
127990618 324129686
479256115 753819852
253766533 449479844
332623760 979143500
122448725 384124626
101854341 491806437
324275294 529171976
378385813 569430598
152484569 322626345
397853336 772523199
126282101 235322141
327610187 686112903
353962429 655163953
391009046 400936407
45488493 815834125
394001259 642294484
111624270 253455511
220990588 255719882
10907106 950118387
177210402 555916808
316351449 741082827
425556581 856116768
421507248 586064719
93888922 642637722
99843590 473754317
8213634 764585393
488097822 840278753
435342015 842508745
349406673 484900634
280010853 370443835
400888260 691956893
421748251 737067324
305905572 386773097
435191289 887843065
260846393 731941575
445631476 519474101
59915010 237909218
306805801 381681659
324432467 859919996
279649964 564769173
118888227 313212102
302008280 466227315
321239164 872789513
207077522 456470830
242838944 464459846
43481253 51762643
208198294 523145398
47696526 364130319
179957324 441551904
50523163 83566712
478585845 765208335
75756080 429669067
475218138 630450638
55559381 939697803
240414829 549868781
420846535 916723099
329104468 908085028
150336667 828238028

Error Message:

Traceback (most recent call last):
  File "test.py", line 10, in <module>
    for num in range(start,end+1):
MemoryError

Upvotes: 0

Views: 1651

Answers (2)

Blckknght
Blckknght

Reputation: 104682

The reason you're running out of memory is because in Python 2, range allocates a list to hold all of the values you requested. If you request a very wide range, you'll get a very large list.

One possible solution is to use xrange instead of range. xrange returns an iterable object that yields each value, but it doesn't allocate all the values up front, rather it only calculates them as they are needed. This makes it much less memory intensive. The behavior of xrange has become the behavior of range in Python 3.

Now, even with xrange, you may find that your code runs very slowly. That's because you're iterating over very long xranges, and performing a very large number of square roots (which are rather computationally expensive). If you want to do better, you need a new algorithm.

A good place to start is to realize that the number of integers between x and y that are exact squares is the same as the number of integers between sqrt(x) and sqrt(y). This doesn't require any iteration at all, and only needs two square roots to be taken, regardless of the size of the interval.

So, rather than looping from start to end, just compute the result directly:

result = math.floor(math.sqrt(end)) - math.ceil(math.sqrt(start)) + 1

Upvotes: 1

niyasc
niyasc

Reputation: 4490

range(start, end + 1) is not able to generate all numbers between your input cases. So it is better to use a while loop instead.

import math
import fileinput


for line in fileinput.input():
    if type(line) == str:
        string= line.split(' ')
        if len(string) == 2:
            start,end = int(string[0]),int(string[1])
            counter = 0
        print start, end + 1
        i = start
        while i <= end:
                sqrt,floor = math.sqrt(i),math.floor(math.sqrt(i))
                if sqrt == floor:
                    counter += 1
        print counter
        i += 1

            print counter

Upvotes: 0

Related Questions