Given ‘N’ which represent the regular N sided polygon. Two children are standing on the vertex ‘A’ and ‘B’ of this Regular N sided polygon. The task is to determine the number of that vertex another person should stand on so that the sum of the minimum jumps required to reach A and minimum jumps required to reach B is minimized.
Note:
- The vertices of this regular polygon are number from 1 to N in a clockwise manner.
- If there are multiple answers, output the least numbered vertex.
Examples:
Input: N = 6, A = 2, B = 4 Output: Vertex = 3 Explanation: The another person should stand on 3rd vertex. As from 3rd vertex, 1 jump is required to reach A and 1 jump is required to reach B. (See figure above) Input: N = 4, A = 1, B = 2 Output: Vertex = 3 Explanation: The another person should stand on 3rd or 4th vertex. But, as mentioned above we have to print least numbered vertex that's why the output is 3.
Approach:
- Simply calculate jumps from each vertex except vertices A and B as on that vertices children are standing and store their sum in sum variable.
- Finally, print that position from where the sum of jumps is minimum.
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to find out the// number of that verticesint vertices(int N, int A, int B){ int position = 0; int minisum = INT_MAX; int sum = 0; for (int i = 1; i <= N; i++) { // Another person can't stand on // vertex on which 2 children stand. if (i == A || i == B) continue; // calculating minimum jumps from // each vertex. else { int x = abs(i - A); int y = abs(i - B); // Calculate sum of jumps. sum = x + y; if (sum < minisum) { minisum = sum; position = i; } } } return position;}// Driver codeint main(){ int N = 3, A = 1, B = 2; // Calling function cout << "Vertex = " << vertices(N, A, B); return 0;} |
Java
// Java implementation of above approachclass GFG { // Function to find out the// number of that verticesstatic int vertices(int N, int A, int B){ int position = 0; int minisum = Integer.MAX_VALUE; int sum = 0; for (int i = 1; i <= N; i++) { // Another person can't stand on // vertex on which 2 children stand. if (i == A || i == B) continue; // calculating minimum jumps from // each vertex. else { int x = Math.abs(i - A); int y = Math.abs(i - B); // Calculate sum of jumps. sum = x + y; if (sum < minisum) { minisum = sum; position = i; } } } return position;}// Driver codepublic static void main(String[] args){ int N = 3, A = 1, B = 2; // Calling function System.out.println("Vertex = " + vertices(N, A, B));}}// This code contributed by Rajput-Ji |
Python
# Python3 implementation of above approach# Function to find out the# number of that verticesdef vertices(N, A, B): position = 0 miniSum = 10**9 Sum = 0 for i in range(1, N + 1): # Another person can't stand on # vertex on which 2 children stand. if (i == A or i == B): continue # calculating minimum jumps from # each vertex. else: x = abs(i - A) y = abs(i - B) # Calculate Sum of jumps. Sum = x + y if (Sum < miniSum): miniSum = Sum position = i return position# Driver codeN = 3A = 1B = 2# Calling functionprint("Vertex = ",vertices(N, A, B))# This code is contributed by mohit kumar |
C#
// C# implementation of the approach using System;using System.Collections.Generic;class GFG { // Function to find out the // number of that vertices static int vertices(int N, int A, int B) { int position = 0; int minisum = int.MaxValue; int sum = 0; for (int i = 1; i <= N; i++) { // Another person can't stand on // vertex on which 2 children stand. if (i == A || i == B) continue; // calculating minimum jumps from // each vertex. else { int x = Math.Abs(i - A); int y = Math.Abs(i - B); // Calculate sum of jumps. sum = x + y; if (sum < minisum) { minisum = sum; position = i; } } } return position; } // Driver code public static void Main(String[] args) { int N = 3, A = 1, B = 2; // Calling function Console.WriteLine("Vertex = " + vertices(N, A, B)); } } /* This code contributed by PrinciRaj1992 */ |
PHP
<?php// PHP implementation of above approach// Function to find out the// number of that verticesfunction vertices($N, $A, $B){ $position = 0; $minisum = PHP_INT_MAX; $sum = 0; for ($i = 1; $i <= $N; $i++) { // Another person can't stand on // vertex on which 2 children stand. if ($i == $A || $i == $B) continue; // calculating minimum jumps from // each vertex. else { $x = abs($i - $A); $y = abs($i - $B); // Calculate sum of jumps. $sum = $x + $y; if ($sum < $minisum) { $minisum = $sum; $position = $i; } } } return $position;} // Driver code $N = 3; $A = 1; $B = 2; // Calling function echo "Vertex = ",vertices($N, $A,$B); // This code is contributed by Ryuga?> |
Javascript
<script>// Javascript implementation of above approach// Function to find out the// number of that verticesfunction vertices(N, A, B){ var position = 0; var minisum = Number.MAX_VALUE; var sum = 0; for(var i = 1; i <= N; i++) { // Another person can't stand on // vertex on which 2 children stand. if (i == A || i == B) continue; // calculating minimum jumps from // each vertex. else { var x = Math.abs(i - A); var y = Math.abs(i - B); // Calculate sum of jumps. sum = x + y; if (sum < minisum) { minisum = sum; position = i; } } } return position;}// Driver codevar N = 3, A = 1, B = 2;// Calling functiondocument.write("Vertex = " + vertices(N, A, B));// This code is contributed by Ankita saini</script> |
Output:
Vertex = 3
Time Complexity: O(N)
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!
Share your thoughts in the comments
