Problem

Submissions

Hints & solutions

Discuss

Count Of Divisible Pairs

Easy

0/40

Average time to solve is 15m

Contributed by

51 upvotes

Problem statement

You are given two integers ‘N’ and ‘M’. A pair (x, y) is a divisible pair if it satisfies the following conditions:

a) 1 <= x <= ‘N’

b) 1 <= y <= ‘M’

c) x + y is divisible by 5.

Your task is to return the count of all divisible pairs that can be formed from given ‘N’ and ‘M’.

Example :

If N = 3 and M = 5, then { x = 1, y = 4 },  { x = 2, y = 3 },  { x = 3, y = 2 } are the pairs that satisfy the given conditions.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows

The first line of each testcase contains two integers ‘N’ and ‘M’.

Output Format :

For each test case print a single integer denoting the count of divisible pairs.

Output for each test case will be printed in a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 10      
1 <= N, M <= 10^9

Time limit: 1 sec

Sample Input 1 :

2
1 5
2 3

Sample Output 1 :

1
1

Explanation Of Sample Output 1 :

For test case 1 :
Only (1,4) satisfy the given condition.

For test case 2 :
Only (2,3) satisfy the given conditions.

Sample Input 2 :

2
1 3
6 12

Sample Output 2 :

0
14

Hint 1

Hint 2

Try checking the condition for each possible pair.

Approaches (2)

Approach 1

Approach 2

Brute Force

We can create all pairs possible and check the condition of divisibility.

To create all the pairs, for each x in the range [1, N] iterate through all y in the range [1, M].

The steps are as follows :

Initialize count to 0.
Run outer for loop for x from 1 to N
Run inner for loop for y from 1 to M
For each generated pair of (x,y) increment the count if the x+y is divisible by 5.
Return the final value of count.

Time Complexity

O( N*M ), where N is the natural number given in input.

Since we iterate over all N * M possible pairs, Hence the time complexity is O(N*M) .

Space Complexity

O(1)

Since constant space used. Hence the space complexity is O(1).

(100% EXP penalty)

Count Of Divisible Pairs

Console