Find the number of substrings of a numerical string greater than a given num string

Question:
http://qa.geeksforgeeks.org/9744/vinay-queried-interesting-problem-optimization

Input


The first line contains N denoting the length of Target String. This
line is followed by the Target String. The Target String is followed
by an integer Q denoting the number of queries asked. After this Q
lines follow each line containing a Query String.

Output


For each query output the total number of distinct Cruel Pairs that
satisfies the given conditions.

Constraints


1 ≤ N ≤ 5000

1 ≤ Q ≤ 104

Sum of Lengths of all Query Strings ≤ 106

All strings are composed only of '0' - '9'

Sample Input

5
75201
5
78945884875
22
00048
77
501

Sample Output

0
8
8
6
5

Explanation


Query String 1 : No such Pair exist.


Query String 2 : Pairs are (1,2) , (1,3) , (1,4) , (1,5) , (2,3) ,
(2,4) , (2,5) , (3,5)


Query String 5 : Pairs are (1,3) , (1,4) , (1,5) , (2,4) , (2,5)


Time Limit:1.0 sec(s) for each input file. 5s for python


Memory Limit:256 MB


Source Limit:1024 KB

Please review the code and help me with optimization

N = int(raw_input())

target = str(int(raw_input()))

N = len(target)

Q_N = int(raw_input())

queries_list = []
output = []

for x in xrange(Q_N):
    queries_list.append(raw_input())

for x in queries_list:
    d = int(str(int(x))[0])
    x = str(int(x))
    q_l = len(x)
    if q_l > N:
        print 0
        continue
    count = 0
    for i, t in enumerate(target):
        t = int(t)
        temp = 0
        if t > d:
            temp = (N - i) - q_l + 1
        elif t > 0 and t  int(x):
                temp = temp + 1
        if temp > 0:
            count = count + temp

    print count

Since I misunderstood the question. I offer up a second take. I have not convinced myself that log10 will increase the efficacy of the script but I use it anyway to show the concept of using math instead of len on strings.

The code has two generators, one to truncate the number from the left, or moving the X coordinate of the cruel pair. Another generator to move the Y coordinate.

The generator that moves the Y coordinate starts at the same length as the query string is. If the query string is longer it yields 0.

The main function relies on the fact that if the condition are meet, all following conditions in the current substring are meet and we and we can simply add those. This means that the only check done is the check where the is of equal length + 1.

from math import log10

def iterate_number_ints(num):
    length = int(log10(num))+1
    for i in range(length-1):
        yield num%(10**(length))
        if num // 10 ** (length - 2) % 10 == 0:
            yield 0
        length -= 1

def iterate_sub_number(num, lower_limit):
    if num > 0:
        length = int(log10(num))
        lower_limit_length = int(log10(lower_limit+1))
        for n in range(lower_limit_length, length+1):
            yield num//(10**(length-n))
    yield 0

def main():

    queries = [int(x) for x in ["78945884875", "22", "00048", "77", "501"]]
    target = 75201

    for k in range(len(queries)):
        ans = 0
        for t in iterate_number_ints(target):
            if t == 0:
                continue
            length_t = int(log10(t))
            for l in iterate_sub_number(t, queries[k]):
                if l == 0:
                    continue
                length_l = int(log10(l))
                if l > queries[k]:
                    ans += length_t-length_l+1
                    break

        print(queries[k], ans)

if __name__ == '__main__':
    main()

It might not be a complete solution, i can't test it, but it reduces the numbers of cases that are checked. But i should give some pointers.

StackExchange Code Review Q#143631, answer score: 2