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

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