-3
\$\begingroup\$

I am writing a code which returns something like 1^k + 2^k + 3^k......n-1 where k be any number.Below is my code.I am getting a memory error.How do I optimise it. Sample test case for wrong error:

1 10000000000000000 400

#!/bin/python    
    import sys



def highwayConstruction(n, k):
    # Complete this function
    sum=0
    for i in range(1,n-1):
        sum+=(n-i)**k
    return sum    

q = int(raw_input().strip())
print "Qw"
for a0 in xrange(q):
    n, k = raw_input().strip().split(' ')
    n, k = [long(n), int(k)]
    result = highwayConstruction(n, k)
    print result
| improve this question | | | | |
\$\endgroup\$
1
\$\begingroup\$

Try using xrange instead of range. They both provide a way to generate a list of integers for you to use. The only difference is that range returns a Python list object and xrange returns an xrange object. You get the MemoryError because the list you are trying to generate is too big. I tried running it with xrange and it didn't crash. I waited for about 30 minutes and it's still running.

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ but now it gives me a timeout error. \$\endgroup\$ – Leo B Jacob Nov 19 '17 at 18:48
  • \$\begingroup\$ This probably means your cpu can't handle this calculation. \$\endgroup\$ – Mixhab Nov 19 '17 at 18:50
  • \$\begingroup\$ is there any other way to do this like bitwise implementation. \$\endgroup\$ – Leo B Jacob Nov 19 '17 at 19:15

Not the answer you're looking for? Browse other questions tagged or ask your own question.