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

By | 16.02.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 : :

```import math
for i in range(input()):
n,m=map(int,raw_input().split())
if m/2 <= n:
print 0
continue
k=m/2-n
j=int(math.ceil(m/2.0))-n
a=(k+1)*(j+1)
if m%2==0 or (m-n)%2==0:
a-=1
print a```

OUTPUT : :

`>`

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

SOURCE CODE IN  C++ : :

```#include<iostream>
#include<cstring>
using namespace std;

int main()
{
long long int i,n,m,t,p,count,sum,e,s,d;
cin>>t;

for(i=0;i<t;i++)
{
sum=0;
e=0;
cin>>n>>m;
p=(m-n)*(m-n+1);
long long int arr[p/2];
s=n+1;
d=n;
while(s<=m)
{

if(s==d)
{
s++;
d=n;
}
else if(s/d==1)
{
d++;
}
else
{
arr[e]=s/d;
e++;
d++;
}

}

int freq[e];
std::memset(freq,-1,e*sizeof(int));

for(int x=0; x<e; x++)
{
count = 1;
for(int y=x+1; y<e; y++)
{
if((arr[x]>1)&&(arr[x]==arr[y]))
{
count++;
freq[y] = 0;
}
}
if(freq[x]!=0)
{
freq[x] = count;
}
if(freq[x]>1)
{
sum=sum+freq[x];
}
}

cout<<sum<<endl;
}

return 0;
}```

OUTPUT : :

```3

2 6
3

2 20
80

2 100
2400

Process returned 0``` 