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

 

0 0 votes
Article Rating
Category: Advance Programs C++ Programming Tricky Q Tags: ,

About Tunde A

My name is Tunde Ajetomobi, a Tech Enthusiast and Growth Hacker. I enjoy creating helpful content that solves problem across different topics. Codezclub is my way of helping young aspiring programmers and students to hone their skills and find solutions on fundamental programming languages.

Subscribe
Notify of
guest

0 Comments
Inline Feedbacks
View all comments