find if a number divisible by the input numbers

Question

Given two numbers a and b, we have to find the nth number which is divisible by a or b.

The format looks like below:

Input: First line consists of an integer T, denoting the number of test cases. Second line contains three integers a, b and N

Output: For each test case, print the Nth number in a new line.

Constraints:

1≤t≤105

1≤a,b≤104

1≤N≤10

Sample Input

1

2 3 10

Sample Output

15

Explanation

The numbers which are divisible by 2 or 3 are: 2,3,4,6,8,9,10,12,14,15 and the 10th number is 15.

For single test case input 2000 3000 100000 it is taking more than one second to complete. I want to know if I can get the results in less than 1 second. Is there a time efficient approach to this problem, maybe if we can use some data structure and algorithms here?

test_case=input()

if int(test_case)<=100000 and  int(test_case)>=1:
    for p in range(int(test_case)):
        count=1
        j=1

        inp=list(map(int,input().strip('').split()))
        if inp[0]<=10000 and  inp[0]>=1 and  inp[1]<=10000 and  inp[1]>=1 and inp[1]<=1000000000 and  inp[1]>=1:
            while(True ):
             if count<=inp[2] :
               k=j
               if j%inp[0]==0 or j%inp[1] ==0:
                   count=count+1
                   j=j+1

               else       :
                   j=j+1
             else:
                 break
            print(k)     
        else:
            break

Answer 1

You really need to make your code easier to read, and more consistant.

• I highly advise you learn all of PEP8 and follow it, so that your fellow Python developers can read your code with ease. And not cringe when you start using one and three spaces as indentation.
• I highly advise you get one of the linters avaliable for Python.
• Use functions, they help people know the scope of your code. I don't need to know about count and j when getting input.
• Rather than using list(map(fn, it)) you can use a list comprehension, [fn(i) for i in it]. This is generally the prefered way.
• Use sugar when provided, j=j+1, looks like a mess. Applying PEP8 would change it to j = j + 1, but you can always use +=, to get j += 1. Reducing the amount we need to read.
• There's no need for one of your else's. If you have if ...: ... a += 1 else: a += 1, then you can remove the else and move the a += 1 to run either way.
• It's advised to use gaurd statements, rather than follow the arrow anti-pattern. if count<=inp[2] : could be inverted, followed with the break, and the rest of the code doesn't have another indentation level.

In all I'd highly advise changing your code to something like the following:

def get_nth_multiple(a, b, limit):
    count = 1
    j = 1
    while True:
        if count > limit:
            break

        k=j
        if j%a == 0 or j%b == 0:
            count += 1
        j += 1
    return k


test_case = int(input())
if 1<= test_case <= 100000:
    for _ in range(int(test_case)):
        a, b, limit = [int(i) for i in input().split()]
        if 1 <= a <= 10000 and 1 <= b <= 10000:
            print(get_nth_multiple(a, b, limit))
        else:
            break

---

This is good, however, I'm not sold on the if statements outside the function. I personally would just remove them, as they're not needed.

I'd also change get_nth_multiple. Say you were asked to get the tenth multiple of five, you'd just do \$5 * 10 = 50\$. However you could make a function that returns all multiples of five, and only take the tenth. Something like next(islice(count(5, 5), 10 - 1, None)). And so, you only really need to merge two count(n, n)'s together to make one list, which you can then take the wanted multiple from.

This should sound simple, however, you also have to account for the fact that count is an iterator, not an iterable. And so you have to make a 'peek' list, that contains the next values of a and b. Which can be implemened as:

from itertools import count, islice

def get_multiples(*nums):
    sources = [count(i, i) for i in nums]
    peek = [next(source) for source in sources]
    while True:
        num = min(peek)
        yield num
        peek = [
            next(source) if i == num else i
            for i, source in zip(peek, sources)
        ]

def get_nth_multiple(a, b, limit):
    return islice(get_multiples(a, b), limit - 1, None)


test_case = int(input())
for _ in range(int(test_case)):
    a, b, limit = [int(i) for i in input().split()]
    print(get_nth_multiple(a, b, limit))

Answer 2

I'm not an advanced programmer, but I have some suggestions I think could improve the performance of your code:

1) In the first line you make test_case = input() and then you use this variable 3 times calling int(). Instead, you could use test_case = int(input()), so you'd call this function just once.

2) I don't understand the use of .strip('') here. At least in Python 3.5.2 I ran the code wihout the strip('') and it works just fine.

3) In the first if statement inside the for loop you test the minimum and maximum values of inp[1] twice. You probably wanted to test inp[2] in the last part.

4) Here:

     if count<=inp[2] :
       k=j
       if j%inp[0]==0 or j%inp[1] ==0:
           count=count+1
           j=j+1

       else       :
           j=j+1

No matter the result, j = j+1 (you can write this j+=1 by the way!), so you could write this:

 if count<=inp[2] :
   k=j

   if j%inp[0]==0 or j%inp[1] ==0:
       count=count+1

   #add 1 to j no matter what
   j+=1

5) You made a while loop that evaluates true and put an if statement that may break it right after it. Instead of doing that, you may test the condition of the if statement in the while loop itself writing while count<=inp[2]: and removing the else statement that breaks the loop.

6) (edited) That k variable is actually unecessary. If you set j to 0 in the beginning of the first for loop, and add 1 to j in the beginning of the while loop, you will get the desired result without the need of an extra variable.

With these modifications, the program would be like:

test_case=int(input())

if test_case<=100000 and  test_case>=1:
    for p in range(test_case):
        count=1
        j=0

        inp=list(map(int,input().split()))

        if inp[0]<=10000 and  inp[0]>=1 and  inp[1]<=10000 and  inp[1]>=1 and inp[2]<=1000000000 and  inp[2]>=1:
             while count<=inp[2]:            

               j=j+1

               if j%inp[0]==0 or j%inp[1] ==0:
                   count=count+1

             print(j)     
        else:
            break

I know these are minor changes, but I believe some of them may save some CPU and I hope they're useful for you.