Adjacent element arrangement in Circular Array
Given a circular array arr[] of size N where the last element is adjacent to the first element, the task is to arrange an array where the adjacent element’s absolute difference is 1. Return “YES” Otherwise “NO“.
Examples:
Input: N = 6, arr[] = {1, 1, 2, 2, 2, 3}
Output: YES
Explanation: {2, 1, 2, 1, 2, 3} is one of the possible rearrangements.
Approach: This can be solved with the following idea:
Check the parity of each element, and store them in different vectors. Check whether the absolute difference between even and odd elements is 1 or not.
Below are the steps involved:
- Initialize two vectors even and odd.
- Store even elements in even and odd in odd vectors.
- If the size of both vectors is different, Return “NO“.
- Check for each odd [i] – even [i], the difference is one or not, for each i.
- Return “YES“, if 1 for everyone.
Below is the implementation of the code:
C++
// C++ Implementation #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to check whether we can rearrange string check( int n, int arr[]) { vector< int > odd; vector< int > even; for ( int i = 0; i < n; i++) { // Check if even or odd if (arr[i] % 2 == 0) { even.push_back(arr[i]); } else { odd.push_back(arr[i]); } } // If parity of element is not same if (odd.size() != even.size()) { return "NO"; } // Check for each element for ( int i = 0; i < odd.size(); i++) { if ( abs (odd[i] - even[i]) != 1) { return "NO"; } } return "YES"; } // Driver code int main() { int N = 6; int arr[] = { 1, 1, 2, 2, 2, 3 }; // Function Call cout << check(N, arr); return 0; } |
Java
import java.util.ArrayList; import java.util.List; public class Main { // Function to check whether we can rearrange static String check( int n, int [] arr) { List<Integer> odd = new ArrayList<>(); List<Integer> even = new ArrayList(); for ( int i = 0 ; i < n; i++) { // Check if even or odd if (arr[i] % 2 == 0 ) { even.add(arr[i]); } else { odd.add(arr[i]); } } // If the parity of elements is not the same if (odd.size() != even.size()) { return "NO" ; } // Check for each element for ( int i = 0 ; i < odd.size(); i++) { if (Math.abs(odd.get(i) - even.get(i)) != 1 ) { return "NO" ; } } return "YES" ; } // Driver code public static void main(String[] args) { int N = 6 ; int [] arr = { 1 , 1 , 2 , 2 , 2 , 3 }; // Function Call System.out.println(check(N, arr)); } } |
Python3
# Function to check whether we can rearrange the array def check(n, arr): odd = [] even = [] # Separate elements into odd and even lists for i in range (n): if arr[i] % 2 = = 0 : even.append(arr[i]) else : odd.append(arr[i]) # If the count of odd and even elements is not the same, it's not possible if len (odd) ! = len (even): return "NO" # Check if adjacent elements have an absolute difference of 1 for i in range ( len (odd)): if abs (odd[i] - even[i]) ! = 1 : return "NO" return "YES" # Driver code if __name__ = = "__main__" : N = 6 arr = [ 1 , 1 , 2 , 2 , 2 , 3 ] # Function call print (check(N, arr)) |
C#
// C# code for the above approach using System; using System.Collections.Generic; public class Program { // Function to check whether we can rearrange static string Check( int n, int [] arr) { List< int > odd = new List< int >(); List< int > even = new List< int >(); for ( int i = 0; i < n; i++) { // Check if even or odd if (arr[i] % 2 == 0) { even.Add(arr[i]); } else { odd.Add(arr[i]); } } // If the parity of elements is not the same if (odd.Count != even.Count) { return "NO" ; } // Check for each element for ( int i = 0; i < odd.Count; i++) { if (Math.Abs(odd[i] - even[i]) != 1) { return "NO" ; } } return "YES" ; } // Entry point public static void Main( string [] args) { int N = 6; int [] arr = { 1, 1, 2, 2, 2, 3 }; // Function Call Console.WriteLine(Check(N, arr)); } } |
Javascript
// JavaScript code for the above approach // Function to check whether we can rearrange function check(n, arr) { let odd = []; let even = []; for (let i = 0; i < n; i++) { // Check if even or odd if (arr[i] % 2 === 0) { even.push(arr[i]); } else { odd.push(arr[i]); } } // If parity of element is not same if (odd.length !== even.length) { return "NO" ; } // Check for each element for (let i = 0; i < odd.length; i++) { if (Math.abs(odd[i] - even[i]) !== 1) { return "NO" ; } } return "YES" ; } const N = 6; const arr = [1, 1, 2, 2, 2, 3]; // Function Call console.log(check(N, arr)); // This code is contributed by Abhinav Mahajan (abhinav_m22) |
Output
YES
Time Complexity: O(N)
Auxilairy Space: O(N)
Contact Us