Minimum operations for adjacent E and E+1 pairing
Last Updated :
19 Oct, 2023
Given an integer N and an array arr[], containing numbers from 0 to (2*N-1). In one operation you can swap the position of any two integers in the array. Find the minimum number of operations required to make an array in such a format that, each even number 'E' is adjacent to 'E+1' i.e. 0 is adjacent to 1, 2 is adjacent to 3, and so on.
Examples:
Input: N = 2, arr[] = {3, 0, 2, 1}
Output: 1
Explanation: Swap values 0 and 2, after that new array will be {3, 2, 0, 1} where 0 is adjacent to 1 and 2 is adjacent to 3.
Input: N = 3, arr[] = {1, 0, 3, 2, 4, 5}
Output: 0
Explanations: Clearly all even number E is adjacent to E+1.
Approach: We can use Disjoint-Set-Union (DSU) data structure to solve this question efficiently.
Construct a graph where each vertex has two indexes 2i and 2i+1 for each 0 <= i < N. Now we form an edge between two vertices iff the index values of the vertices give 'E' in one vertex and 'E+1' in other vertex, where E is an even number. The total number of vertices - The total number of connected components in the graph will be our answer.
Follow the steps to solve the problem:
- First, implement the DSU data structure using make(), find(), and Union() functions, and a parent array/map as per need.
- For each, i from 0 to N, initialize the parent for vertex pair {2i, 2i+1} as itself using the make() function of DSU.
- Find all the vertex pairs such that one pair has an even 'E' and the other has 'E+1', and combine these vertices using the Union operation of DSU.
- Find the number of connected components of the DSU, this can be done by finding the unique number of parents existing in the DSU
- Print (number of vertices - number of connected components) as your answer.
Below is the implementation of the above algorithm.
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// Parent map to store parent of each vertex
map<pair<int, int>, pair<int, int> > parent;
// This function is used to initialize DSU
void make(pair<int, int> i) { parent[i] = { i }; }
// This function is used to find the parent of
// each component
pair<int, int> find(pair<int, int> v)
{
if (parent[v] == v)
return v;
return parent[v] = find(parent[v]);
}
// This function is used to Merge two
// components together
void Union(pair<int, int> a, pair<int, int> b)
{
a = find(a);
b = find(b);
if (a != b) {
parent[b] = a;
}
}
// This function solves our problem
int solve(vector<int>& arr, int n)
{
// Initializing the DSU
for (int i = 0; i < n; i++) {
pair<int, int> p = { 2 * i, 2 * i + 1 };
make(p);
}
// For all vertex i and j
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)
continue;
// vertex formed by i
pair<int, int> a = { 2 * i, 2 * i + 1 };
// vertex formed by j
pair<int, int> b = { 2 * j, 2 * j + 1 };
// Condition to find E and E+1 vertices
if ((arr[2 * i] / 2 == arr[2 * j] / 2)
|| (arr[2 * i] / 2 == arr[2 * j + 1] / 2)
|| (arr[2 * i + 1] / 2 == arr[2 * j] / 2)
|| (arr[2 * i + 1] / 2
== arr[2 * j + 1] / 2)) {
// Union of valid vertices.
Union(a, b);
}
}
}
map<pair<int, int>, int> comp;
// Finding total unique components.
for (int i = 0; i < n; i++) {
comp[find({ 2 * i, 2 * i + 1 })]++;
}
// n-unique components is our answer
return n - comp.size();
}
// Driver function
int main()
{
int N = 2;
vector<int> arr = { 3, 0, 2, 1 };
// Function call
cout << solve(arr, N) << endl;
return 0;
}
import java.util.*;
public class Main {
static Map<Pair, Pair> parent;
// Custom class to represent pairs
static class Pair {
int first;
int second;
public Pair(int first, int second) {
this.first = first;
this.second = second;
}
@Override
public int hashCode() {
return Objects.hash(first, second);
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null || getClass() != obj.getClass())
return false;
Pair other = (Pair) obj;
return first == other.first && second == other.second;
}
}
// This function is used to initialize DSU
static void make(Pair i) {
parent.put(i, i);
}
// This function is used to find the parent of each component
static Pair find(Pair v) {
if (parent.get(v).equals(v))
return v;
return parent.put(v, find(parent.get(v)));
}
// This function is used to Merge two components together
static void Union(Pair a, Pair b) {
a = find(a);
b = find(b);
if (!a.equals(b)) {
parent.put(b, a);
}
}
// This function solves our problem
static int solve(List<Integer> arr, int n) {
parent = new HashMap<>();
// Initializing the DSU
for (int i = 0; i < n; i++) {
Pair p = new Pair(2 * i, 2 * i + 1);
make(p);
}
// For all vertex i and j
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)
continue;
// vertex formed by i
Pair a = new Pair(2 * i, 2 * i + 1);
// vertex formed by j
Pair b = new Pair(2 * j, 2 * j + 1);
// Condition to find E and E+1 vertices
if ((arr.get(2 * i) / 2 == arr.get(2 * j) / 2)
|| (arr.get(2 * i) / 2 == arr.get(2 * j + 1) / 2)
|| (arr.get(2 * i + 1) / 2 == arr.get(2 * j) / 2)
|| (arr.get(2 * i + 1) / 2 == arr.get(2 * j + 1) / 2)) {
// Union of valid vertices.
Union(a, b);
}
}
}
Map<Pair, Integer> comp = new HashMap<>();
// Finding total unique components.
for (int i = 0; i < n; i++) {
comp.put(find(new Pair(2 * i, 2 * i + 1)), comp.getOrDefault(find(new Pair(2 * i, 2 * i + 1)), 0) + 1);
}
// n-unique components is our answer
return n - comp.size();
}
// Driver function
public static void main(String[] args) {
int N = 2;
List<Integer> arr = Arrays.asList(3, 0, 2, 1);
// Function call
System.out.println(solve(arr, N));
}
}
// This code is contributed by akshitaguprzj3
class Pair:
def __init__(self, first, second):
self.first = first
self.second = second
def __hash__(self):
return hash((self.first, self.second))
def __eq__(self, other):
if self is other:
return True
if not isinstance(other, Pair):
return False
return self.first == other.first and self.second == other.second
def make(i, parent):
parent[i] = i
def find(v, parent):
if parent[v] == v:
return v
parent[v] = find(parent[v], parent)
return parent[v]
def union(a, b, parent):
a = find(a, parent)
b = find(b, parent)
if a != b:
parent[b] = a
def solve(arr, n):
parent = {}
# Initializing the DSU
for i in range(n):
p = Pair(2 * i, 2 * i + 1)
make(p, parent)
# For all vertex i and j
for i in range(n):
for j in range(n):
if i == j:
continue
# vertex formed by i
a = Pair(2 * i, 2 * i + 1)
# vertex formed by j
b = Pair(2 * j, 2 * j + 1)
# Condition to find E and E+1 vertices
if (
(arr[2 * i] // 2 == arr[2 * j] // 2)
or (arr[2 * i] // 2 == arr[2 * j + 1] // 2)
or (arr[2 * i + 1] // 2 == arr[2 * j] // 2)
or (arr[2 * i + 1] // 2 == arr[2 * j + 1] // 2)
):
# Union of valid vertices.
union(a, b, parent)
comp = {}
# Finding total unique components.
for i in range(n):
component = find(Pair(2 * i, 2 * i + 1), parent)
comp[component] = comp.get(component, 0) + 1
# n-unique components is our answer
return n - len(comp)
if __name__ == "__main__":
N = 2
arr = [3, 0, 2, 1]
# Function call
print(solve(arr, N))
using System;
using System.Collections.Generic;
class Pair
{
public int first;
public int second;
public Pair(int first, int second)
{
this.first = first;
this.second = second;
}
public override int GetHashCode()
{
return (this.first, this.second).GetHashCode();
}
public override bool Equals(object obj)
{
if (this == obj)
return true;
if (!(obj is Pair))
return false;
Pair other = (Pair)obj;
return this.first == other.first && this.second == other.second;
}
}
class Program
{
static void Make(int i, Dictionary<Pair, Pair> parent)
{
parent[new Pair(i * 2, i * 2 + 1)] = new Pair(i * 2, i * 2 + 1);
}
static Pair Find(Pair v, Dictionary<Pair, Pair> parent)
{
if (parent[v].Equals(v))
return v;
parent[v] = Find(parent[v], parent);
return parent[v];
}
static void Union(Pair a, Pair b, Dictionary<Pair, Pair> parent)
{
a = Find(a, parent);
b = Find(b, parent);
if (!a.Equals(b))
parent[b] = a;
}
static int Solve(int[] arr, int n)
{
var parent = new Dictionary<Pair, Pair>();
// Initializing the DSU
for (int i = 0; i < n; i++)
{
Make(i, parent);
}
// For all vertex i and j
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i == j)
continue;
// Vertex formed by i
Pair a = new Pair(i * 2, i * 2 + 1);
// Vertex formed by j
Pair b = new Pair(j * 2, j * 2 + 1);
// Condition to find E and E+1 vertices
if ((arr[i * 2] / 2 == arr[j * 2] / 2) ||
(arr[i * 2] / 2 == arr[j * 2 + 1] / 2) ||
(arr[i * 2 + 1] / 2 == arr[j * 2] / 2) ||
(arr[i * 2 + 1] / 2 == arr[j * 2 + 1] / 2))
{
// Union of valid vertices.
Union(a, b, parent);
}
}
}
var comp = new Dictionary<Pair, int>();
// Finding total unique components.
for (int i = 0; i < n; i++)
{
Pair component = Find(new Pair(i * 2, i * 2 + 1), parent);
comp[component] = comp.ContainsKey(component) ? comp[component] + 1 : 1;
}
// n-unique components is our answer
return n - comp.Count;
}
static void Main(string[] args)
{
int N = 2;
int[] arr = { 3, 0, 2, 1 };
// Function call
Console.WriteLine(Solve(arr, N));
}
}
<script>
// Custom class to represent pairs
class Pair {
constructor(first, second) {
this.first = first;
this.second = second;
}
hashCode() {
return JSON.stringify([this.first, this.second]);
}
equals(obj) {
if (this === obj) return true;
if (obj == null || typeof obj !== 'object' || obj.constructor !== Pair) return false;
return this.first === obj.first && this.second === obj.second;
}
}
// Initialize DSU
function make(i, parent) {
parent.set(i, i);
}
// Find the parent of each component
function find(v, parent) {
if (parent.get(v).equals(v)) return v;
return find(parent.get(v), parent);
}
// Merge two components together
function Union(a, b, parent) {
a = find(a, parent);
b = find(b, parent);
if (!a.equals(b)) {
parent.set(b, a);
}
}
// Solve the problem
function solve(arr, n) {
let parent = new Map();
// Initializing the DSU
for (let i = 0; i < n; i++) {
let p = new Pair(2 * i, 2 * i + 1);
make(p, parent);
}
// For all vertices i and j
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (i === j) continue;
// Vertex formed by i
let a = new Pair(2 * i, 2 * i + 1);
// Vertex formed by j
let b = new Pair(2 * j, 2 * j + 1);
// Condition to find E and E+1 vertices
if (
arr[2 * i] / 2 === arr[2 * j] / 2 ||
arr[2 * i] / 2 === arr[2 * j + 1] / 2 ||
arr[2 * i + 1] / 2 === arr[2 * j] / 2 ||
arr[2 * i + 1] / 2 === arr[2 * j + 1] / 2
) {
// Union of valid vertices.
Union(a, b, parent);
}
}
}
let comp = new Map();
// Finding total unique components.
for (let i = 0; i < n; i++) {
let component = find(new Pair(2 * i, 2 * i + 1), parent);
comp.set(component, (comp.get(component) || 0) + 1);
}
// n-unique components is our answer
return n - comp.size;
}
// Driver function
let N = 2;
let arr = [3, 0, 2, 1];
// Function call
console.log(solve(arr, N));
</script>
// code contributed by shinjanpatra
Time Complexity: O(N^2 logN)
Auxiliary Space: O(N)
Similar Reads
Minimizing Swaps for Adjacent pair Sum Difference in Permutation
Given a permutation P of length n. The task is to find the minimum number of swaps required in the permutation such that the difference between the maximum value of (P[i] + P[i+1]) and the minimum value of (P[i] + P[i+1]), where 0 <= i <= n-2, is minimized. Note: In other words, we want to rea
8 min read
Minimize sum of Array formed using given relation between adjacent elements
Given a binary string S of length N, consisting of 0's and 1's, the task is to find the minimum sum of the array of non-negative integers of length N+1 created by following the below conditions: If the ith number in the given binary string is 0, then the (i + 1)th number in the array must be less th
11 min read
Maximum Sum pair of non adjacent elements in array
Given an array arr[] of distinct Integers, find the pair with maximum sum such that both elements of the pair are not adjacent in the array Examples: Input: arr[] = {7, 3, 4, 1, 8, 9}Output: 9 7Explanation: Pair with maximum sum is (8, 9). But since both elements are adjacent, it is not a valid pair
8 min read
Minimum number of swaps required for arranging pairs adjacent to each other
There are n-pairs and therefore 2n people. everyone has one unique number ranging from 1 to 2n. All these 2n persons are arranged in random fashion in an Array of size 2n. We are also given who is partner of whom. Find the minimum number of swaps required to arrange these pairs such that all pairs b
15 min read
Minimize the count of adjacent pairs with different parity
Given an array arr of size N containing some integers from the range [1, N] and -1 in the remaining indices, the task is to replace -1 by the remaining integers from [1, N] such that the count of pairs of adjacent elements with different parity is minimized. Examples: Input: arr = {-1, 5, -1, 2, 3}
10 min read
Find the minimised number using given operations
Given an array arr[] of n elements. In one operation you can pick two indices i and j, such that arr[i] ≥ arr[j] and replace the value of arr[i] with (arr[i] - arr[j]), the task is to minimize the values of the array after performing any number of such operations. Examples: Input: n = 3, arr[] = {3,
12 min read
Minimum deletion such that Xor of adjacent digits is atmost 1
Given a string S consisting of N digits, the task is to find the minimum number of deletions such that the bitwise Xor of any two adjacent digits of the remaining string is at most 1. Examples: Input: S = "24244"Output: 2?Explanation: We can delete both the 2's to make the string "444", which satisf
5 min read
Count of product operations to make adjacent Array elements of different parity
Given an array arr[] consisting of N elements. At each operation, you can select any 2 adjacent elements in which both the elements are of the same parity and then delete both of them, and insert their product in the same position, the task is to find the minimum number of operations needed for this
8 min read
De-arrangements for minimum product sum of two arrays
Given two arrays A[] and B[] of same size n. We need to first permute any of arrays such that the sum of product of pairs( 1 element from each) is minimum. That is SUM ( Ai*Bi) for all i is minimum. We also need to count number of de-arrangements present in original array as compared to permuted arr
5 min read
Minimum number of increment operations required to make two Strings equal
Given two strings S1 and S2 of the same length containing characters ranging from '0' to '9', the task is to return the minimum number of operations required to make two strings equal by following the below operations: Increment any two characters from the string by 1.If it is not possible to make t
8 min read