# Count ways of choosing a pair with maximum difference

Given an array of n integers, we need to find the no. of ways of choosing pairs with maximum difference.

Examples:

Input : a[] = {3, 2, 1, 1, 3} Output : 4 Explanation:- Here, the maximum difference you can find is 2 which is from (1, 3). No. of ways of choosing it: 1) Choosing the first and third elements, 2) Choosing the first and fourth elements, 3) Choosing the third and fifth elements, 4) Choosing the fourth and fifth elements. Hence ans is 4. Input : a[] = {2, 4, 1, 1} Output : 2 Explanation:- Here, the maximum difference is 3 from (1, 4). No. of ways choosing it: 1) Choosing the second and third elements, 2) Choosing the second and fourth elements. Hence ans is 2.

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**.

**Naive Approach : **A Simple solution is to find the minimum element and maximum element to find the maximum difference. Then we can find the no. of ways of choosing a pair by running two loops. In the inner loop, check if the two elements(one in outer loop and other in inner loop) are making maximum difference, if yes increase the count.at last output the count.

Time Complexity: O(n^2)

Auxiliary Space: O(1)**Efficient approach:**

An efficient approach will be:

- Case I (if all the elements are equal): The ans is no. of ways of choosing 2 elements from a set of n elements which is n(n-1)/2.
- Case II (If all the elements are not equal) : The answer is product of count of no. of minimum elements(c1) and count of no. of maximum elements(c2), i.e., c1*c2

## C++

`// CPP Code to find no. of Ways of choosing` `// a pair with maximum difference` `#include <bits/stdc++.h>` `using` `namespace` `std;` `int` `countPairs(` `int` `a[], ` `int` `n)` `{` ` ` `// To find minimum and maximum of` ` ` `// the array` ` ` `int` `mn = INT_MAX;` ` ` `int` `mx = INT_MIN;` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `mn = min(mn, a[i]);` ` ` `mx = max(mx, a[i]);` ` ` `}` ` ` `// to find the count of minimum and` ` ` `// maximum elements` ` ` `int` `c1 = 0;` ` ` `int` `c2 = 0; ` `// Count variables` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `if` `(a[i] == mn)` ` ` `c1++;` ` ` `if` `(a[i] == mx)` ` ` `c2++;` ` ` `}` ` ` `// condition for all elements equal` ` ` `if` `(mn == mx)` ` ` `return` `n * (n - 1) / 2;` ` ` `else` ` ` `return` `c1 * c2;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `a[] = { 3, 2, 1, 1, 3 };` ` ` `int` `n = ` `sizeof` `(a) / ` `sizeof` `(a[0]);` ` ` `cout << countPairs(a, n);` ` ` `return` `0;` `}` |

## Java

`// Java Code to find no. of Ways of choosing` `// a pair with maximum difference` `import` `java.util.*;` `class` `GFG {` ` ` `static` `int` `countPairs(` `int` `a[], ` `int` `n)` ` ` `{` ` ` `// To find minimum and maximum of` ` ` `// the array` ` ` `int` `mn = Integer.MAX_VALUE;` ` ` `int` `mx = Integer.MIN_VALUE;` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++) {` ` ` `mn = Math.min(mn, a[i]);` ` ` `mx = Math.max(mx, a[i]);` ` ` `}` ` ` `// to find the count of minimum and` ` ` `// maximum elements` ` ` `int` `c1 = ` `0` `;` ` ` `int` `c2 = ` `0` `; ` `// Count variables` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++) {` ` ` `if` `(a[i] == mn)` ` ` `c1++;` ` ` `if` `(a[i] == mx)` ` ` `c2++;` ` ` `}` ` ` `// condition for all elements equal` ` ` `if` `(mn == mx)` ` ` `return` `n * (n - ` `1` `) / ` `2` `;` ` ` `else` ` ` `return` `c1 * c2;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `a[] = { ` `3` `, ` `2` `, ` `1` `, ` `1` `, ` `3` `};` ` ` `int` `n = a.length;` ` ` `System.out.print(countPairs(a, n));` ` ` `}` `}` `// This code is contributed by Anant Agarwal.` |

## Python3

`# Python Code to find no.` `# of Ways of choosing` `# a pair with maximum difference` `def` `countPairs(a, n):` ` ` `# To find minimum and maximum of` ` ` `# the array` ` ` `mn ` `=` `+` `2147483647` ` ` `mx ` `=` `-` `2147483648` ` ` `for` `i ` `in` `range` `(n):` ` ` `mn ` `=` `min` `(mn, a[i])` ` ` `mx ` `=` `max` `(mx, a[i])` ` ` ` ` ` ` `# to find the count of minimum and` ` ` `# maximum elements` ` ` `c1 ` `=` `0` ` ` `c2 ` `=` `0` `# Count variables` ` ` `for` `i ` `in` `range` `(n):` ` ` `if` `(a[i] ` `=` `=` `mn):` ` ` `c1` `+` `=` `1` ` ` `if` `(a[i] ` `=` `=` `mx):` ` ` `c2` `+` `=` `1` ` ` ` ` ` ` `# condition for all elements equal` ` ` `if` `(mn ` `=` `=` `mx):` ` ` `return` `n` `*` `(n ` `-` `1` `) ` `/` `/` `2` ` ` `else` `:` ` ` `return` `c1 ` `*` `c2` `# Driver code` `a ` `=` `[ ` `3` `, ` `2` `, ` `1` `, ` `1` `, ` `3` `]` `n ` `=` `len` `(a)` `print` `(countPairs(a, n))` `# This code is contributed` `# by Anant Agarwal.` |

## C#

`// C# Code to find no. of Ways of choosing` `// a pair with maximum difference` `using` `System;` `class` `GFG {` ` ` `static` `int` `countPairs(` `int` `[] a, ` `int` `n)` ` ` `{` ` ` `// To find minimum and maximum of` ` ` `// the array` ` ` `int` `mn = ` `int` `.MaxValue;` ` ` `int` `mx = ` `int` `.MinValue;` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `mn = Math.Min(mn, a[i]);` ` ` `mx = Math.Max(mx, a[i]);` ` ` `}` ` ` `// to find the count of minimum and` ` ` `// maximum elements` ` ` `int` `c1 = 0;` ` ` `int` `c2 = 0; ` `// Count variables` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `if` `(a[i] == mn)` ` ` `c1++;` ` ` `if` `(a[i] == mx)` ` ` `c2++;` ` ` `}` ` ` `// condition for all elements equal` ` ` `if` `(mn == mx)` ` ` `return` `n * (n - 1) / 2;` ` ` `else` ` ` `return` `c1 * c2;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `Main()` ` ` `{` ` ` ` ` `int` `[] a = { 3, 2, 1, 1, 3 };` ` ` `int` `n = a.Length;` ` ` ` ` `Console.WriteLine(countPairs(a, n));` ` ` `}` `}` `// This code is contributed by vt_m.` |

## PHP

`<?php` `// PHP Code to find no. of Ways of choosing` `// a pair with maximum difference` `function` `countPairs(` `$a` `, ` `$n` `)` `{` ` ` `// To find minimum and maximum of` ` ` `// the array` ` ` `$mn` `= PHP_INT_MAX;` ` ` `$mx` `= PHP_INT_MIN;` ` ` `for` `(` `$i` `= 0; ` `$i` `< ` `$n` `; ` `$i` `++) {` ` ` `$mn` `= min(` `$mn` `, ` `$a` `[` `$i` `]);` ` ` `$mx` `= max(` `$mx` `, ` `$a` `[` `$i` `]);` ` ` `}` ` ` `// to find the count of minimum and` ` ` `// maximum elements` ` ` `$c1` `= 0;` ` ` `$c2` `= 0; ` `// Count variables` ` ` `for` `(` `$i` `= 0; ` `$i` `< ` `$n` `; ` `$i` `++) {` ` ` `if` `(` `$a` `[` `$i` `] == ` `$mn` `)` ` ` `$c1` `++;` ` ` `if` `(` `$a` `[` `$i` `] == ` `$mx` `)` ` ` `$c2` `++;` ` ` `}` ` ` `// condition for all elements equal` ` ` `if` `(` `$mn` `== ` `$mx` `)` ` ` `return` `$n` `* (` `$n` `- 1) / 2;` ` ` `else` ` ` `return` `$c1` `* ` `$c2` `;` `}` `// Driver code` ` ` `$a` `= ` `array` `( 3, 2, 1, 1, 3 );` ` ` `$n` `= ` `count` `(` `$a` `);` ` ` `echo` `countPairs(` `$a` `, ` `$n` `);` `// This code is contributed by anuj_67.` `?>` |

## Javascript

`<script>` `// JavaScript Code to find no. of Ways of choosing` `// a pair with maximum difference` ` ` `function` `countPairs(a, n)` ` ` `{` ` ` ` ` `// To find minimum and maximum of` ` ` `// the array` ` ` `let mn = Number.MAX_VALUE;` ` ` `let mx = Number.MIN_VALUE;` ` ` `for` `(let i = 0; i < n; i++) {` ` ` `mn = Math.min(mn, a[i]);` ` ` `mx = Math.max(mx, a[i]);` ` ` `}` ` ` ` ` `// to find the count of minimum and` ` ` `// maximum elements` ` ` `let c1 = 0;` ` ` `let c2 = 0; ` `// Count variables` ` ` `for` `(let i = 0; i < n; i++) {` ` ` `if` `(a[i] == mn)` ` ` `c1++;` ` ` `if` `(a[i] == mx)` ` ` `c2++;` ` ` `}` ` ` ` ` `// condition for all elements equal` ` ` `if` `(mn == mx)` ` ` `return` `n * (n - 1) / 2;` ` ` `else` ` ` `return` `c1 * c2;` ` ` `}` ` ` ` ` `// Driver Code` ` ` `let a = [ 3, 2, 1, 1, 3 ];` ` ` `let n = a.length;` ` ` `document.write(countPairs(a, n));` ` ` `</script>` |

Output:

4

**Time Complexity:** Time complexity to find minimum and maximum is **O(n)** and Time Complexity to find count of minimum and maximum is **O(n)**

Overall Time complexity : O(n)

Auxiliary Space : O(1)

This article is contributed by **Harsha mogali**. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.