2
\$\begingroup\$

The question states:

Given an integer A, and two indices Li, Ri. Find if the number from A which is bounded by the two indices is divisible by 7?

For example if A = 357753
indices Li = 3, Ri = 4, then the number is 77, which is divisible.

My program give a time limit exceeded when executed for larger numbers. Are there any other performance improvement can be done in my code. Or the whole method is wrong for the solution. Any help would be appreciated. "q" is the number of indices that will be provided as input.

First code (not optimized):

inp = raw_input()

q = input()



temp = ""

for i in range(q):

    l, r = map(int, raw_input().split())

    temp =  int(inp[l - 1:r])

    if temp % 7 == 0:

        print "YES"
    else:

        print "NO"

My second program is:

inp = input()

q = input()

temp = 0
length = len(str(inp)) - 1
for i in range(q):

    left, right = map(int, raw_input().split())

    temp = inp
    end = length - right + 1
    temp = temp / (10 ** end)
    mul = 1
    final = 0

    while right >= left:

        cur = temp % 10
        temp = temp / 10
        right -= 1
        #print cur
        final += (cur * mul)
        mul = mul * 10


    if final % 7 == 0:

        print "YES"
    else:

        print "NO"
\$\endgroup\$
7
  • 1
    \$\begingroup\$ Some more information might be useful: In what number range are the given numbers? How many indices Li, Ri are given for a single number A? If this is a public challenge, can you provide a link? \$\endgroup\$
    – Martin R
    Jul 31, 2016 at 9:19
  • \$\begingroup\$ What are your test numbers? \$\endgroup\$
    – zondo
    Jul 31, 2016 at 11:10
  • \$\begingroup\$ what does q do? \$\endgroup\$ Jul 31, 2016 at 13:39
  • 1
    \$\begingroup\$ @OscarSmith q is the number of test cases. \$\endgroup\$ Jul 31, 2016 at 14:15
  • \$\begingroup\$ I'm putting this question on hold because I suspect that it is part of an ongoing programming contest. I'll reopen it in a week (or earlier, if given evidence that it isn't). (See this other question posted shortly after). \$\endgroup\$ Jul 31, 2016 at 15:52

1 Answer 1

6
\$\begingroup\$

I'm not sure why you think the second one is "optimized"; the former at least looks faster to me.

Don't name variables temp - it tells you nothing about the actual job of the variable. q is also a bad name'; num_iters is clearer, and i is not used so just use an underscore instead.

Don't pre-initialize values, in this case temp. Assign to it only when you need to.

Don't use input - always use raw_input and explicit conversions.

Then you have

inp = raw_input()
num_iters = int(raw_input())

for _ in range(num_iters):
    l, r = map(int, raw_input().split())
    temp = int(inp[l - 1:r])

    if temp % 7 == 0:
        print "YES"
    else:
        print "NO"

which is simple enough to basically be ideal. A more advanced programmer might want to handle errors or put code into functions, but the advantages of those only really apply to larger programs.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ The one other thing I would add is don't name variables l. it looks like a 1, and thus can be quite confusing. I would suggest left or li (left index). \$\endgroup\$ Jul 31, 2016 at 16:19
  • \$\begingroup\$ Thanks for reviewing my question. But, i don't know why it came as TLE for all inputs. And since it is a past contest it is not allowing to test it now. And i will definitely try to improve my coding method next time . \$\endgroup\$
    – susil95
    Jul 31, 2016 at 17:23
  • \$\begingroup\$ @susil95 You probably can't get much faster on CPython. Chances are the bottleneck is the print, but I'm just guessing. \$\endgroup\$
    – Veedrac
    Jul 31, 2016 at 17:30
  • \$\begingroup\$ Does stdout write will give an speeder output? Because sometimes in contest they recommend to so that? \$\endgroup\$
    – susil95
    Jul 31, 2016 at 17:36
  • \$\begingroup\$ @susil95 Depending on how you do it, possibly. I'd have to time it to know for sure, though. \$\endgroup\$
    – Veedrac
    Jul 31, 2016 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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