Remainder Quotient Problem – Find all the combinations between n and m

By | February 16, 2017

Remainder Quotient – Find all combinations between n & m


Andrew and James are best friends and are fond of puzzles. Andrew challenged James to solve a mathematical problem and promised him to pay $100 if he gives the correct answer.

The problem is that James will be given T pairs of (n,m). Now, all the combinations of all the numbers between n and m(including limits) are taken two at a time.

The left digit in the combination is divided by the right digit in the combination. If the quotient is greater than 1 then the quotient is taken into further consideration.

Frequency of the quotients (greater than 1) is counted and the frequencies greater than1 are added giving the final answer.


Write a code for James to help him make the calculation and win $100.


Explanation

For T number of test cases you are given two numbers n,m .

Find the total number of pairs(a,b) having integral part of quotient greater than 1,where quotient=a/b.

CONSTRAINTS:

1<=T<=10^5

1<=n<=m<=10^5

Sample Input:

2

2 6

2 15

Sample Output:

3

42

Detailed Explanation

2 is the number of test cases.

2,6 and 2,15 are the two test cases.

consider the first test case 2,6

All the numbers between 2 & 6 are considered (including 2 and 6) and pairs are formed:

(2,3) (2,4) (2,5) (2,6)

(3,2) (3,4) (3,5) (3,6)

(4,2) (4,3) (4,5) (4,6)

(5,2) (5,3) (5,4) (5,6)

(6,2) (6,3) (6,4) (6,5)

All the left digits in pair are divided by the right digit in the pair.

0 0 0 0

1 0 0 0

2 1 0 0

2 1 1 0

3 2 1 1

Quotients greater than 1 are considered.

2, 2, 3, 2

Frequency of (2) = 3

Frequency of (3) = 1

Since, we have to consider the frequencies > 1

Hence, we will ignore Frequency of (3) i.e. = 1

And sum all the other Frequencies that are > 1

The Frequencies > 1 are 3 (i.e Frequency of 2)

Therefore, answer is 3 for the first test case.

Time Limit:3.0 sec(s) for each input file.
Memory Limit:256 MB
Source Limit:1024 KB

SOURCE CODE IN  PYTHON : :

 

OUTPUT : :

 

>> ================= RESTART: C:\Users\Second.py ================= 3 2 15 42 2 7 6 2 5000 6245000 >>>

 


 

SOURCE CODE IN  C++ : :

 

 

OUTPUT : :

 

 

Leave a Reply