Check if every index i has an index j such that sum of elements in both directions are equal
Given a circular array of size N. The task is to check if, for every index, i starting from 0 to N-1, there exists an index j that is not equal to i such that the sum of all the numbers in the clockwise direction from i to j is equal to the sum of all numbers in the anticlockwise direction from i to j.
Examples:
Input: a[] = {1, 4, 1, 4}
Output: Yes
The circular array is 1->4->1->4.
for index 0, j will be 2, then sum of elements from index 0 to 2 in clockwise direction will be 1 + 4 + 1 = 6 and the sum of elements from index 0 to 2 in anticlockwise direction will be 1 + 4 + 1 = 6.
for index 1, j will be 3, then sum of elements from index 1 to 3 in clockwise direction will be 4 + 1 + 4 = 9 and the sum of elements from index 1 to 3 in anticlockwise direction will be 4 + 1 + 4 = 9.
for index 2, j will be 0, then sum of elements from index 2 to 0 in clockwise direction will be 1 + 4 + 1 = 6 and the sum of elements from index 2 to 0 in anticlockwise direction will be 1 + 4 + 1 = 6
for index 3, j will be 1, then sum of elements from index 3 to 1 in clockwise direction will be 4 + 1 + 4 = 9 and the sum of elements from index 3 to 1 in anticlockwise direction will be 4 + 1 + 4 = 9Input: a[] = {1, 1, 1, 1, 1, 1}
Output: Yes
Approach:
- When N is odd, the answer will be “NO” always as it is not possible to find an index j for every index i.
- If N is even, then check if the opposite element is exactly same for every index i, then the answer is “YES”.
- If the any of the index’s opposite element i.e., a[(i+(n/2))] is not equal to a[i], then the answer will be “NO”.
Implementation:
C++
// C++ program to check if the // number lies in given range #include <bits/stdc++.h> using namespace std; // Function that returns the maximum element. bool check( int a[], int n) { // check for odd if (n % 2 == 1) return false ; // check if the opposite element is same // as a[i] for ( int i = 0; i < n / 2; i++) { if (a[i] != a[i + (n / 2)]) return false ; } return true ; } // Driver code int main() { int a[] = { 1, 4, 1, 4 }; int n = sizeof (a) / sizeof (a[0]); if (check(a, n)) cout << "YES" ; else cout << "NO" ; return 0; } |
Java
//Java program to check if the //number lies in given range public class GFG { //Function that returns the maximum element. static boolean check( int a[], int n) { // check for odd if (n % 2 == 1 ) return false ; // check if the opposite element is same // as a[i] for ( int i = 0 ; i < n / 2 ; i++) { if (a[i] != a[i + (n / 2 )]) return false ; } return true ; } //Driver code public static void main(String[] args) { int a[] = { 1 , 4 , 1 , 4 }; int n = a.length; if (check(a, n)) System.out.println( "YES" ); else System.out.println( "NO" ); } } |
Python 3
# Python 3 Program to check if the # number lies in given range # Function that returns the maximum element. def check(a, n) : # check for odd if n % 2 = = 1 : return False # check if the opposite element is same # as a[i] for i in range (n / / 2 ) : if a[i] ! = a[i + (n / / 2 )]: return False return True # Driver Code if __name__ = = "__main__" : a = [ 1 , 4 , 1 , 4 ] n = len (a) if check(a, n) : print ( "YES" ) else : print ( "NO" ) # This code is contributed by ANKITRAI1 |
C#
// C# program to check if the // number lies in given range class GFG { // Function that returns the // maximum element. static bool check( int [] a, int n) { // check for odd if (n % 2 == 1) return false ; // check if the opposite // element is same as a[i] for ( int i = 0; i < ( int )n / 2; i++) { if (a[i] != a[i + ( int )(n / 2)]) return false ; } return true ; } // Driver code public static void Main() { int [] a = new int []{ 1, 4, 1, 4 }; int n = a.Length; if (check(a, n)) System.Console.WriteLine( "YES" ); else System.Console.WriteLine( "NO" ); } } // This code is contributed by mits |
PHP
<?php // PHP program to check if the // number lies in given range // Function that returns the // maximum element. function check( $a , $n ) { // check for odd if ( $n % 2 == 1) return false; // check if the opposite // element is same as a[i] for ( $i = 0; $i < $n / 2; $i ++) { if ( $a [ $i ] != $a [ $i + ( $n / 2)]) return false; } return true; } // Driver code $a = array ( 1, 4, 1, 4 ); $n = sizeof( $a ); if (check( $a , $n )) echo "YES" ; else echo "NO" ; // This code is contributed // by Akanksha Rai(Abby_akku) |
Javascript
<script> // Javascript program to check if the // number lies in given range // Function that returns the maximum element. function check( a, n) { // check for odd if (n % 2 == 1) return false ; // check if the opposite element is same // as a[i] for ( var i = 0; i < parseInt(n / 2); i++) { if (a[i] != a[i + parseInt(n / 2)]) return false ; } return true ; } // Driver code var a = [ 1, 4, 1, 4 ]; var n = a.length; if (check(a, n)) document.write( "YES" ); else document.write( "NO" ); // This code is contributed by rrrtnx. </script> |
YES
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(1)