Distinct adjacent elements in an array
Given an array, find whether it is possible to obtain an array having distinct neighbouring elements by swapping two neighbouring array elements.
Examples:
Input : 1 1 2 Output : YES swap 1 (second last element) and 2 (last element), to obtain 1 2 1, which has distinct neighbouring elements . Input : 7 7 7 7 Output : NO We can't swap to obtain distinct elements in neighbor .
To obtain an array having distinct neighbouring elements is possible only, when the frequency of most occurring element is less than or equal to half of size of array i.e ( <= (n+1)/2 ). To make it more clear consider different examples
1st Example : a[] = {1, 1, 2, 3, 1} We can obtain array {1, 2, 1, 3, 1} by swapping (2nd and 3rd) element from array a. Here 1 occurs most and its frequency is 3 . So that 3 <= ((5+1)/2) . Hence, it is possible.
Below is the implementation of this approach.
C++
// C++ program to check if we can make // neighbors distinct. #include <bits/stdc++.h> using namespace std; void distinctAdjacentElement( int a[], int n) { // map used to count the frequency // of each element occurring in the // array map< int , int > m; // In this loop we count the frequency // of element through map m . for ( int i = 0; i < n; ++i) m[a[i]]++; // mx store the frequency of element which // occurs most in array . int mx = 0; // In this loop we calculate the maximum // frequency and store it in variable mx. for ( int i = 0; i < n; ++i) if (mx < m[a[i]]) mx = m[a[i]]; // By swapping we can adjust array only // when the frequency of the element // which occurs most is less than or // equal to (n + 1)/2 . if (mx > (n + 1) / 2) cout << "NO" << endl; else cout << "YES" << endl; } // Driver program to test the above function int main() { int a[] = { 7, 7, 7, 7 }; int n = sizeof (a) / sizeof (a[0]); distinctAdjacentElement(a, n); return 0; } |
Python3
# Python program to check if we can make # neighbors distinct. def distantAdjacentElement(a, n): # dict used to count the frequency # of each element occurring in the # array m = dict () # In this loop we count the frequency # of element through map m for i in range (n): if a[i] in m: m[a[i]] + = 1 else : m[a[i]] = 1 # mx store the frequency of element which # occurs most in array . mx = 0 # In this loop we calculate the maximum # frequency and store it in variable mx. for i in range (n): if mx < m[a[i]]: mx = m[a[i]] # By swapping we can adjust array only # when the frequency of the element # which occurs most is less than or # equal to (n + 1)/2 . if mx > (n + 1 ) / / 2 : print ( "NO" ) else : print ( "YES" ) # Driver Code if __name__ = = "__main__" : a = [ 7 , 7 , 7 , 7 ] n = len (a) distantAdjacentElement(a, n) # This code is contributed by # sanjeev2552 |
C#
// C# program to check if we can make // neighbors distinct. using System; using System.Collections.Generic; class GFG { public static void distinctAdjacentElement( int [] a, int n) { // map used to count the frequency // of each element occurring in the // array Dictionary< int , int > m = new Dictionary< int , int >(); // In this loop we count the frequency // of element through map m . for ( int i = 0; i < n; ++i) { // checks if map already // contains a[i] then // update the previous // value by incrementing // by 1 if (m.ContainsKey(a[i])) { int x = m[a[i]] + 1; m[a[i]] = x; } else { m[a[i]] = 1; } } // mx store the frequency // of element which // occurs most in array . int mx = 0; // In this loop we calculate // the maximum frequency and // store it in variable mx. for ( int i = 0; i < n; ++i) { if (mx < m[a[i]]) { mx = m[a[i]]; } } // By swapping we can adjust array only // when the frequency of the element // which occurs most is less than or // equal to (n + 1)/2 . if (mx > (n + 1) / 2) { Console.WriteLine( "NO" ); } else { Console.WriteLine( "YES" ); } } // Main Method public static void Main( string [] args) { int [] a = new int [] {7, 7, 7, 7}; int n = 4; distinctAdjacentElement(a, n); } } // This code is contributed // by Shrikant13 |
Java
// Java program to check if we can make // neighbors distinct. import java.io.*; import java.util.HashMap; import java.util.Map; class GFG { static void distinctAdjacentElement( int a[], int n) { // map used to count the frequency // of each element occurring in the // array HashMap<Integer,Integer> m = new HashMap<Integer, Integer>(); // In this loop we count the frequency // of element through map m . for ( int i = 0 ; i < n; ++i){ // checks if map already contains a[i] then // update the previous value by incrementing // by 1 if (m.containsKey(a[i])){ int x = m.get(a[i]) + 1 ; m.put(a[i],x); } else { m.put(a[i], 1 ); } } // mx store the frequency of element which // occurs most in array . int mx = 0 ; // In this loop we calculate the maximum // frequency and store it in variable mx. for ( int i = 0 ; i < n; ++i) if (mx < m.get(a[i])) mx = m.get(a[i]); // By swapping we can adjust array only // when the frequency of the element // which occurs most is less than or // equal to (n + 1)/2 . if (mx > (n + 1 ) / 2 ) System.out.println( "NO" ); else System.out.println( "YES" ); } // Driver program to test the above function public static void main (String[] args) { int a[] = { 7 , 7 , 7 , 7 }; int n = 4 ; distinctAdjacentElement(a, n); } } // This code is contributed by Amit Kumar |
Javascript
<script> // JavaScript program to check if we can make // neighbors distinct. function distinctAdjacentElement(a, n) { // map used to count the frequency // of each element occurring in the // array let m = new Map(); // In this loop we count the frequency // of element through map m . for (let i = 0; i < n; ++i) { m[a[i]]++; if (m.has(a[i])) { m.set(a[i], m.get(a[i]) + 1) } else { m.set(a[i], 1) } } // mx store the frequency of element which // occurs most in array . let mx = 0; // In this loop we calculate the maximum // frequency and store it in variable mx. for (let i = 0; i < n; ++i) if (mx < m.get(a[i])) mx = m.get(a[i]); // By swapping we can adjust array only // when the frequency of the element // which occurs most is less than or // equal to (n + 1)/2 . if (mx > Math.floor((n + 1) / 2)) document.write( "NO" + "<br>" ); else document.write( "YES<br>" ); } // Driver program to test the above function let a = [7, 7, 7, 7]; let n = a.length; distinctAdjacentElement(a, n); </script> |
Output
NO
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us