Given a number n, we need to find the maximum number of times n circles intersect.
Examples:
Input : n = 2
Output : 2Input : n = 3
Output : 6
Description and Derivation
As we can see in above diagram, for each pair of circles, there can be maximum two intersection points. Therefore if we have n circles then there can be nC2 pairs of circles in which each pair will have two intersections. So by this, we can conclude that by looking at all possible pairs of circles the mathematical formula can be made for the maximum number of intersections by n circles is given by 2 * nC2.
2 * nC2 = 2 * n * (n – 1)/2 = n * (n-1)
C++
// CPP program to find maximum number of // intersections of n circles#include <bits/stdc++.h>using namespace std;// Returns maximum number of intersectionsint intersection(int n){ return n * (n - 1);}int main(){ cout << intersection(3) << endl; return 0;}// This code is contributed by // Manish Kumar Rai. |
Java
// Java program to find maximum number of // intersections of n circlesimport java.io.*;public class GFG { // for the calculation of 2*(nC2) static int intersection(int n) { return n * (n - 1); } public static void main(String[] args) throws IOException { System.out.println(intersection(3)); }}// This code is contributed by // Manish Kumar Rai |
Python3
# python program to find maximum number of # intersections of n circles# Returns maximum number of intersectionsdef intersection(n): return n * (n - 1);# Driver codeprint(intersection(3))# This code is contributed by Sam007 |
C#
// C# program to find maximum number of // intersections of n circlesusing System;class GFG { // for the calculation of 2*(nC2) static int intersection(int n) { return n * (n - 1); }// Driver Codepublic static void Main(){ Console.WriteLine(intersection(3));}}// This code is contributed by Sam007 |
PHP
<?php// php program to find maximum number of // intersections of n circles// Returns maximum number of intersectionsfunction intersection($n){ return $n * ($n - 1);} // Driver codeecho intersection(3);// This code is contributed by Sam007?> |
Javascript
<script>// Javascript program to find maximum number of // intersections of n circles// Returns maximum number of intersectionsfunction intersection(n){ return n * (n - 1);} // Driver codedocument.write(intersection(3));// This code is contributed by _saurabh_jaiswal</script> |
Output:
6
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
