Teams

Easy
0/40
Average time to solve is 20m
profile
Contributed by
18 upvotes

Problem statement

You hosted a great party and invited all of your friends. You have an infinite number of friends. Since you can’t remember all of their names, you have given each of them an ‘id’ numbered from ‘1’ to ‘∞’. You decided to play a game ‘T’ times. Each time you select an even number of friends having ‘id’ from the range ‘L’ to ‘R’. You play the game by dividing all of your friends into ‘(R - L + 1) / 2’ teams, i.e. every team consists of two friends, and every friend is a member of exactly one team. But there is a problem. Two friends will only form a team if the gcd of their ‘id’ is 1. I.e. gcd(i, j) must be 1 and ‘L’ <= i < j <= ‘R’.

For each game. If you can divide the friends into ‘(R - L + 1) / 2’ teams, print the resulting pairs,i.e. Pair of friend’s id who are forming a team, else print no solution exists. If there are multiple solutions, you can print any of them.

Note: The solution function returns a single value, and based on your answer, the output will either be 1 or 0.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains ‘T’, denoting the number of games.
For each Test :
    The first line contains two space-separated integers, ‘L’ and ‘R’, denoting the friend’s ids’ range that will play the game.
Output Format: 
For each test case.
If a solution exists, the following ‘(R - L + 1) / 2’ lines should contain two space-separated integers whose gcd is 1, denoting the friend’s ids that will form a team.
Constraints - 
1<= ‘T’ <= 10
1 <= ‘L’ < ‘R’ <= 10 ^ 18.
2 <= ‘R - L + 1’ <= 10 ^ 5.
‘R - L + 1’ is always even.

Time Limit: 1 sec
Sample Input 1:
2
1 8
1 4
Sample Output-1
1
2 7
4 1
3 8
6 5
1
1 4
3 2
Explanation for Sample Input 1:
For Case 1:
    Gcd of all the pairs are 1, and no number is in more than one pair.
For Case 2:
    Gcd of all the pairs are 1, and no number is in more than one pair.
Sample Input 2:
2
3 8
1 2
Sample Output-2
1
4 7
3 8
6 5
1
1 2
Hint

How the difference between two numbers is related to their gcd?

Approaches (1)
Maths

Approach: GCD of every two adjacent numbers is always 1. Say ‘n’ has a divisor ‘q’, for which n / q = p. If we divide ‘n + 1’ by ‘q’, we will get (n + 1) / q = (n / q) + (1 / q) = p + (1 / q), thus for all q ≠ 1, ‘n + 1’ will not be divisible by ‘q’. Hence, gcd(n, n + 1) = 1. So

we can always divide our friends to play the game. Every neighbouring friends will form a team.

Algorithm:

  • Print ‘1’.
  • Iterate using a for loop from i = ‘L’ to ‘R’ with an increment of 2.
    • Print ‘i’ and ‘i + 1’.
Time Complexity

O(R - L), where L and R are the given input.

 

We are iterating using a ‘for’ loop from ‘L’ to ‘R’. Hence the overall complexity is O(R - L).

Space Complexity

O(1).

We are creating a variable to use in the ‘for’ loop. Hence the overall complexity is O(1).

Code Solution
(100% EXP penalty)
Teams
Full screen
Console