Rhezo and divisibility by 7 challenge

There is a big number with N digits and Q questions.


In each question, find if the number formed by the string between
indices Li and Ri is divisible by 7 or not.


Input: First line contains the number consisting of N digits. Next line contains Q, denoting the number of questions. Each of the next Q
lines contains 2 integers a and b.


Output: For each question, print "YES" or "NO", if the number formed by the string between indices a and b is divisible by 7.


Constraints: 1≤N≤105, 1≤Q≤105, 1≤a,b≤N

Full question

def is_divisible_by_7(num):

    if num - num / 7 * 7 == 0:

        return True
    else:

        return False

N = raw_input()

Q = int(raw_input())

for x in xrange(Q):

    a, b = map(int, raw_input().split())

    if is_divisible_by_7(int(N[a - 1:b])):
        print "YES"
    else:
        print "NO"

First regarding style. Python has an official style-guide, PEP8, which recommends having no unnecessary whitespace. It improves readability a lot if you avoid having a blank line between every line. Use them sparingly to set apart larger logical blocks.

The standard way, which is the most efficient, to test for divisibility is the modulus operator, %. This way you don't have to rely on integer division to always be around (which it will not be, it has been removed by full division in python 3.x). You can also directly return the result of the comparison:

def is_divisible_by_7(num):
    return num % 7 == 0

You should put your code in a f __name__ == "__main__" guard and into functions to allow re-usability of your code:

def main():
    N = raw_input()
    Q = int(raw_input())

    for _ in xrange(Q):
        a, b = map(int, raw_input().split())
        num = int(N[a - 1:b])
        print "YES" if num % 7 == 0 else "NO"

if __name__ == "__main__":
    main()

Here I inlined the function is_divisible_by_7, used _ as a place-holder variable which is not used in the loop as customary in Python and used a ternary expression to print the result. You also don't need to use split, in python 2.x map returns a list which can directly be used in tuple-assignment.

Alternatively, if a and b appear repeatedly, caching might help:

def memodict(f):
    """ Memoization decorator for a function taking a single argument"""
    class memodict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret
    return memodict().__getitem__

@memodict
def is_divisible_by_7(indices):
    a, b = map(int, indices.split())
    return "NO" if int(N[a - 1:b]) % 7 else "YES"

N = raw_input()
Q = int(raw_input())
for _ in xrange(Q):
     print is_divisible_by_7(raw_input())

As a third alternative, we could not cache the indices, but the numbers for which we do the divisibility test. This is worthwhile if they repeat and are big.

@memodict
def is_divisible_by_7(n):
    return int(n) % 7 == 0

N = raw_input()
Q = int(raw_input())
for _ in xrange(Q):
     a, b = map(int, raw_input().split())
     print "YES" if is_divisible_by_7(N[a - 1:b]) else "NO"

with the same memodict class as above.

This could be made slightly faster by not printing every line, but aggregating the results first:

N = raw_input()
Q = int(raw_input())
out = []
for _ in xrange(Q):
     a, b = map(int, raw_input().split())
     out.append("YES" if is_divisible_by_7(N[a - 1:b]) else "NO")
print "\n".join(out)

A fourth possibility is to try to exploit a divisibility rule for 7. There are not very nice ones, but I did find this one:


Double the last digit and subtract it from a number made by the other
digits. The result must be divisible by 7. (We can apply this rule to
that answer again) (source)

So we want to recursively test the number. But since it can have up to 10**5 digits, we have to hope that it tires small numbers first, otherwise we run into python's recursion limit. However, we can increase that limit to the number of digits, N.

import sys

MAX_INT = 2**31 - 1

@memodict
def is_divisible_by_7(n_str):
    if n <= MAX_INT:  # mod should be fast enough below this limit
        return int(n_str) % 7 == 0
    return is_divisible_by_7(str(int(n_str[:-1]) - 2*int(n_str[-1])))

N = raw_input()
sys.setrecursionlimit(MAX_INT)  # to allow processing the number
Q = int(raw_input())
for _ in xrange(Q):
     a, b = map(int, raw_input().split())
     print "YES" if is_divisible_by_7(N[a - 1:b]) else "NO"

This does a lot more processing, especially conversions between str and int. But maybe combined with the caching it might do some good.

StackExchange Code Review Q#143202, answer score: 4