# All possible co-prime distinct element pairs within a range [L, R]

Given a range [L, R], the task is to find all possible co-prime pairs from the range such that an element doesn’t appear in more than a single pair.**Examples:**

Input :L=1 ; R=6Output: 3 The answer is 3 [(1, 2) (3, 4) (5, 6)], all these pairs have GCD 1.Input :L=2 ; R=4Output :1 The answer is 1 [(2, 3) or (3, 4)] as '3' can only be chosen for a single pair.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

**Approach:** The key observation of the problem is that the numbers with the difference of ‘1’ are always relatively prime to each other i.e. co-primes.

GCD of this pair is always ‘1’. So, the answer will be (R-L+1)/2 [ (total count of numbers in range) / 2 ]

- If R-L+1 is odd then there will be one element left which can not form a pair.
- If R-L+1 is even then all elements can form pairs.

Below is the implementation of the above approach:

## C++

`// C++ implementation of the approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to count possible pairs` `void` `CountPair(` `int` `L, ` `int` `R)` `{` ` ` `// total count of numbers in range` ` ` `int` `x = (R - L + 1);` ` ` `// Note that if 'x' is odd then` ` ` `// there will be '1' element left` ` ` `// which can't form a pair` ` ` `// printing count of pairs` ` ` `cout << x / 2 << ` `"\n"` `;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `L, R;` ` ` `L = 1, R = 8;` ` ` `CountPair(L, R);` ` ` `return` `0;` `}` |

## Java

` ` `// Java implementation of the approach` `import` `java.util.*;` `class` `solution` `{` `// Function to count possible pairs` `static` `void` `CountPair(` `int` `L, ` `int` `R)` `{` ` ` `// total count of numbers in range` ` ` `int` `x = (R - L + ` `1` `);` ` ` `// Note that if 'x' is odd then` ` ` `// there will be '1' element left` ` ` `// which can't form a pair` ` ` `// printing count of pairs` ` ` `System.out.println(x / ` `2` `+ ` `"\n"` `);` `}` `// Driver code` `public` `static` `void` `main(String args[])` `{` ` ` `int` `L, R;` ` ` `L = ` `1` `; R = ` `8` `;` ` ` `CountPair(L, R);` `}` `}` `//contributed by Arnab Kundu` |

## Python3

`# Python3 implementation of` `# the approach` `# Function to count possible` `# pairs` `def` `CountPair(L,R):` ` ` `# total count of numbers` ` ` `# in range` ` ` `x` `=` `(R` `-` `L` `+` `1` `)` ` ` `# Note that if 'x' is odd then` ` ` `# there will be '1' element left` ` ` `# which can't form a pair` ` ` `# printing count of pairs` ` ` `print` `(x` `/` `/` `2` `)` `# Driver code` `if` `__name__` `=` `=` `'__main__'` `:` ` ` `L,R` `=` `1` `,` `8` ` ` `CountPair(L,R)` ` ` `# This code is contributed by` `# Indrajit Sinha.` |

## C#

`// C# implementation of the approach` `using` `System;` `class` `GFG` `{` `// Function to count possible pairs` `static` `void` `CountPair(` `int` `L, ` `int` `R)` `{` ` ` `// total count of numbers in range` ` ` `int` `x = (R - L + 1);` ` ` `// Note that if 'x' is odd then` ` ` `// there will be '1' element left` ` ` `// which can't form a pair` ` ` `// printing count of pairs` ` ` `Console.WriteLine(x / 2 + ` `"\n"` `);` `}` `// Driver code` `public` `static` `void` `Main()` `{` ` ` `int` `L, R;` ` ` `L = 1; R = 8;` ` ` `CountPair(L, R);` `}` `}` `// This code is contributed` `// by inder_verma..` |

## PHP

`<?php` `// PHP implementation of the above approach` `// Function to count possible pairs` `function` `CountPair(` `$L` `, ` `$R` `)` `{` ` ` `// total count of numbers in range` ` ` `$x` `= (` `$R` `- ` `$L` `+ 1);` ` ` `// Note that if 'x' is odd then` ` ` `// there will be '1' element left` ` ` `// which can't form a pair` ` ` `// printing count of pairs` ` ` `echo` `$x` `/ 2, ` `"\n"` `;` `}` `// Driver code` `$L` `= 1;` `$R` `= 8;` `CountPair(` `$L` `, ` `$R` `);` `// This code is contributed by ANKITRAI1` `?>` |

## Javascript

`<script>` `// Javascript implementation of the approach` `// Function to count possible pairs` `function` `CountPair(L, R)` `{` ` ` ` ` `// total count of numbers in range` ` ` `let x = (R - L + 1);` ` ` ` ` `// Note that if 'x' is odd then` ` ` `// there will be '1' element left` ` ` `// which can't form a pair` ` ` ` ` `// printing count of pairs` ` ` `document.write(x / 2 + ` `"<br/>"` `);` `}` `// driver code` ` ` `let L, R;` ` ` ` ` `L = 1; R = 8;` ` ` `CountPair(L, R);` ` ` `</script>` |

**Output:**

4

**Complexity: O(1)**