Given N points on a plane, where each point has a direct path connecting it to a different point, the task is to count the total number of unique direct paths between the points.
Note: The value of N will always be greater than 2.
Examples:
Input: N = 4
Output: 6
Explanation: Think of 4 points as a 4 sided polygon. There will 4 direct paths (sides of the polygon) as well as 2 diagonals (diagonals of the polygon). Hence the answer will be 6 direct paths.
Input: N = 3
Output: 3
Explanation: Think of 3 points as a 3 sided polygon. There will 3 direct paths (sides of the polygon) as well as 0 diagonals (diagonals of the polygon). Hence the answer will be 3 direct paths.
Approach: The given problem can be solved using an observation that for any N-sided there are (number of sides + number of diagonals) direct paths. For any N-sided polygon, there are N sides and N*(N – 3)/2 diagonals. Therefore, the total number of direct paths is given by N + (N * (N – 3))/2.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the total number// of direct pathsint countDirectPath(int N){ return N + (N * (N - 3)) / 2;}// Driver Codeint main(){ int N = 5; cout << countDirectPath(N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to count the total number// of direct pathsstatic int countDirectPath(int N){ return N + (N * (N - 3)) / 2;}// Driver Codepublic static void main(String []args){ int N = 5; System.out.print(countDirectPath(N));}}// This code is contributed by shivanisinghss2110 |
Python3
# python program for the above approach# Function to count the total number# of direct pathsdef countDirectPath(N): return N + (N * (N - 3)) // 2# Driver Codeif __name__ == "__main__": N = 5 print(countDirectPath(N))# This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;public class GFG{ // Function to count the total number // of direct paths static int countDirectPath(int N) { return N + (N * (N - 3)) / 2; } // Driver Code public static void Main(string []args) { int N = 5; Console.Write(countDirectPath(N)); }}// This code is contributed by AnkThon |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to count the total number // of direct paths function countDirectPath(N) { return N + Math.floor((N * (N - 3)) / 2); } // Driver Code let N = 5; document.write(countDirectPath(N));// This code is contributed by Potta Lokesh </script> |
10
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
