Given two Integers N and M, N indicating equidistant points on circumference of a circle and M indicating number of chords formed with those points. Also given is a vector of pairs C containing position of chords. The task is to rotate the circle by any degree, say X, where 0 < X < 360, and check if the chords of are still symmetric to the original circle.
Example:
Input: N = 12, M = 6, C = {{1, 3}, {3, 7}, {5, 7}, {7, 11}, {9, 11}, {11, 3}};
Output: YESInput: N = 10, M = 3, C = {{1, 2}, {3, 2}, {7, 2}}
Output: NO
Naive Approach: Rotate for every distance K in the range[1, N] and check for each point [a, b] if the rotated point [a + K, b + K] exits.
If there exists any k then print YES else print NO
Time Complexity: O(N*M)
Efficient Approach: It is enough to check for the divisors of N.
Let us suppose if we rotate the image by K units then the whole image will be divided into N/K blocks. Then if K is not a divisor of N, there will be an asymmetric block of length less than K and the image will never be symmetric to the original figure.
So calculate all the divisors of N and check for each chord the rotated chord exists or not.
Below is the implementation of the above approach:
C++
// C++ Program to for the above approach #include <bits/stdc++.h> using namespace std; // Utility function to calculate // divisors of a number in O(sqrt(N)) vector< int > calculateDivisors( int N) { vector< int > div ; for ( int i = 1; i * i <= N; i++) { if (N % i == 0) { div .push_back(i); if (N / i != i && i != 1) { div .push_back(N / i); } } } return div ; } int checkRotationallySymmetric( vector<pair< int , int > > A, int N, int M) { // Maintain a set to check quickly // the presence of a chord set<pair< int , int > > st; for ( int i = 0; i < M; i++) { --A[i].first, --A[i].second; if (A[i].first > A[i].second) { swap(A[i].first, A[i].second); } st.insert(A[i]); } // Calculate the divisors of N. vector< int > div = calculateDivisors(N); // Iterate through the divisors for ( auto x : div ) { bool exist = 1; for ( int i = 0; i < M; i++) { int dx = (A[i].first + x) % N; int dy = (A[i].second + x) % N; if (dx > dy) { swap(dx, dy); } if (st.find({ dx, dy }) != st.end()) { // There exists a valid // chord after rotation } else { // There is no valid chord after rotation exist = false ; break ; } } // if there exist another chord after // rotation for every other chord print // YES and exit the function if (exist) { cout << "YES" ; return 0; } } cout << "NO" ; return 0; } // Driver Code int main() { int N = 12, M = 6; vector<pair< int , int > > C = { { 1, 3 }, { 3, 7 }, { 5, 7 }, { 7, 11 }, { 9, 11 }, { 11, 3 } }; checkRotationallySymmetric(C, N, M); return 0; } |
Java
import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; class GFG { // function to calculate divisors static List<Integer> calculateDivisors( int N) { List<Integer> div = new ArrayList<>(); // checking all possible divisors for ( int i = 1 ; i * i <= N; i++) { if (N % i == 0 ) { div.add(i); if (N / i != i && i != 1 ) { div.add(N / i); } } } return div; } static int checkRotationallySymmetric(List< int []> A, int N, int M) { // Maintain a set to check quickly // the presence of a chord Set<String> st = new HashSet<>(); for ( int i = 0 ; i < M; i++) { A.get(i)[ 0 ] = A.get(i)[ 0 ] - 1 ; A.get(i)[ 1 ] = A.get(i)[ 1 ] - 1 ; if (A.get(i)[ 0 ] > A.get(i)[ 1 ]) { int temp = A.get(i)[ 0 ]; A.get(i)[ 0 ] = A.get(i)[ 1 ]; A.get(i)[ 1 ] = temp; } st.add(A.get(i)[ 0 ] + " " + A.get(i)[ 1 ]); } // Calculate the divisors of N. List<Integer> div = calculateDivisors(N); // Iterate through the divisors for ( int x : div) { boolean exist = true ; for ( int i = 0 ; i < M; i++) { int dx = (A.get(i)[ 0 ] + x) % N; int dy = (A.get(i)[ 1 ] + x) % N; if (dx > dy) { int temp = dx; dx = dy; dy = temp; } if (st.contains(dx + " " + dy)) { // There exists a valid chord after // rotation } else { // There is no valid chord after // rotation exist = false ; break ; } } // if there exist another chord after rotation // for every other chord print YES and exit the // function if (exist) { System.out.println( "YES" ); return 0 ; } } System.out.println( "NO" ); return 0 ; } // Driver Code public static void main(String[] args) { int N = 12 , M = 6 ; List< int []> C = new ArrayList<>(); C.add( new int [] { 1 , 3 }); C.add( new int [] { 3 , 7 }); C.add( new int [] { 5 , 7 }); C.add( new int [] { 7 , 11 }); C.add( new int [] { 9 , 11 }); C.add( new int [] { 11 , 3 }); // function call checkRotationallySymmetric(C, N, M); } } // This code is contributed by phasing17 |
Python3
# Python3 program to implement the approach from typing import List , Tuple def calculateDivisors(N: int ) - > List [ int ]: """ Utility function to calculate divisors of a number in O(sqrt(N)) """ div = [] for i in range ( 1 , int ((N * * 0.5 ) + 1 )): if N % i = = 0 : div.append(i) if N / / i ! = i and i ! = 1 : div.append(N / / i) return div def checkRotationallySymmetric(A: List [ Tuple [ int , int ]], N: int , M: int ) - > None : """ Main function to check rotationally symmetric """ # Maintain a set to check quickly # the presence of a chord st = set () for i in range (M): A[i] = (A[i][ 0 ] - 1 , A[i][ 1 ] - 1 ) if A[i][ 0 ] > A[i][ 1 ]: A[i] = (A[i][ 1 ], A[i][ 0 ]) st.add( tuple (A[i])) # Calculate the divisors of N. div = calculateDivisors(N) # Iterate through the divisors for j in range ( len (div)): exist = True for i in range (M): dx = (A[i][ 0 ] + div[j]) % N dy = (A[i][ 1 ] + div[j]) % N if dx > dy: # swapping dx and dy. temp = dx dx = dy dy = temp if tuple ((dx, dy)) in st: # There exists a valid chord after rotation pass else : # There is no valid chord after rotation exist = False break # if there exist another chord after rotation for every other chord print YES and exit the function if exist: print ( "YES" ) return print ( "NO" ) return # Driver code N = 12 M = 6 C = [( 1 , 3 ), ( 3 , 7 ), ( 5 , 7 ), ( 7 , 11 ), ( 9 , 11 ), ( 11 , 3 )] checkRotationallySymmetric(C, N, M) # This code is contributed by phasing17 |
C#
// C# code to implement the above approach using System; using System.Collections.Generic; class GFG { // function to calculate divisors static List< int > calculateDivisors( int N) { List< int > div = new List< int >(); // checking all possible divisors for ( int i = 1; i * i <= N; i++) { if (N % i == 0) { div.Add(i); if (N / i != i && i != 1) { div.Add(N / i); } } } return div; } static int checkRotationallySymmetric(List<Tuple< int , int > > A, int N, int M) { // Maintain a set to check quickly // the presence of a chord HashSet<Tuple< int , int > > st = new HashSet<Tuple< int , int > >(); for ( int i = 0; i < M; i++) { A[i] = new Tuple< int , int >(A[i].Item1 - 1, A[i].Item2 - 1); if (A[i].Item1 > A[i].Item2) { A[i] = new Tuple< int , int >(A[i].Item2, A[i].Item1); } st.Add(A[i]); } // Calculate the divisors of N. List< int > div = calculateDivisors(N); // Iterate through the divisors foreach ( var x in div) { bool exist = true ; for ( int i = 0; i < M; i++) { int dx = (A[i].Item1 + x) % N; int dy = (A[i].Item2 + x) % N; if (dx > dy) { Tuple< int , int > temp = new Tuple< int , int >(dy, dx); dx = temp.Item1; dy = temp.Item2; } if (st.Contains( new Tuple< int , int >(dx, dy))) { // There exists a valid // chord after rotation } else { // There is no valid chord after // rotation exist = false ; break ; } } // if there exist another chord after // rotation for every other chord print // YES and exit the function if (exist) { Console.WriteLine( "YES" ); return 0; } } Console.WriteLine( "NO" ); return 0; } // Driver Code static void Main( string [] args) { int N = 12, M = 6; List<Tuple< int , int > > C = new List<Tuple< int , int > >{ new Tuple< int , int >(1, 3), new Tuple< int , int >(3, 7), new Tuple< int , int >(5, 7), new Tuple< int , int >(7, 11), new Tuple< int , int >(9, 11), new Tuple< int , int >(11, 3) }; // function call checkRotationallySymmetric(C, N, M); } } // This code is contributed by phasing17 |
Javascript
// JavaScript Program to for the above approach // Utility function to calculate // divisors of a number in O(sqrt(N)) function calculateDivisors(N) { let div = new Array(); for (let i = 1; i * i <= N; i++) { if (N % i == 0) { div.push(i); if (Math.floor(N / i) != i && i != 1) { div.push(Math.floor(N / i)); } } } return div; } function checkRotationallySymmetric( A, N, M) { // Maintain a set to check quickly // the presence of a chord let st = new Set(); for (let i = 0; i < M; i++) { A[i][0] = A[i][0] - 1; A[i][1] = A[i][1] - 1; if (A[i][0] > A[i][1]) { let temp = A[i][0]; A[i][0] = A[i][1]; A[i][1] = temp; } st.add(A[i].join( '' )); } // Calculate the di ors of N. let div = calculateDivisors(N); // Iterate through the divisors for (let j = 0; j < div.length; j++){ let exist = true ; for (let i = 0; i < M; i++) { let dx = (A[i][0] + div[j]) % N; let dy = (A[i][1] + div[j]) % N; if (dx > dy) { // swapping dx and dy. let temp = dx; dx = dy; dy = temp; } if (st.has([dx, dy].join( '' ))) { // There exists a valid // chord after rotation } else { // console.log([dx, dy]); // There is no valid chord after rotation exist = false ; break ; } } // if there exist another chord after // rotation for every other chord print // YES and exit the function if (exist) { console.log( "YES" ); return 0; } } console.log( "NO" ); return 0; } // Driver Code let N = 12, M = 6; let C = [[1, 3 ], [3, 7 ], [5, 7 ], [7, 11 ], [9, 11], [11, 3 ]]; checkRotationallySymmetric(C, N, M); // The code is contributed by Gautam goel (gautamgoel962) |
YES
Time Complexity: O(M*sqrt(N)*log M)
Space Complexity: O(M)