Data Modelling & AI Data Structure & Algorithm

Minimum operations for adjacent E and E+1 pairing

28 July 2024

0

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;
}

Java

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

Python3

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))

C#

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));
    }
}

Javascript

<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

Output

Time Complexity: O(N^2 logN)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Commit to GfG’s Three-90 Challenge! Purchase a course, complete 90% in 90 days, and save 90% cost click here to explore.

Last Updated :
19 Oct, 2023

Previous

<!–

8 Min Read | Java

–>

Connecting employees from different companies

Next

<!–

8 Min Read | Java

–>

Check whether the frequency of the elements in the Array is unique or not

Share your thoughts in the comments

Minimum operations for adjacent E and E+1 pairing

C++

Java

Python3

C#

Javascript

Run Local AWS Cloud Stack using LocalStack on Linux

Learn Terraform Automation in 3 days using Video Courses

How To Expose Ansible AWX Service using Nginx Ingress

LEAVE A REPLY Cancel reply

Most Popular

Vietnam’s Success in Software Outsourcing

Install Python 3 / Python 2.7 on Rocky Linux 8 |AlmaLinux 8

How To Manage Angular JS Projects using Angular CLI

How To Install PHP 8.2 on Ubuntu 22.04|20.04|18.04

Recent Comments

EDITOR PICKS

Vietnam’s Success in Software Outsourcing

Install Python 3 / Python 2.7 on Rocky Linux 8 |AlmaLinux 8

How To Manage Angular JS Projects using Angular CLI

POPULAR POSTS

Vietnam’s Success in Software Outsourcing

Install Python 3 / Python 2.7 on Rocky Linux 8 |AlmaLinux 8

How To Manage Angular JS Projects using Angular CLI

POPULAR CATEGORY

ABOUT US

FOLLOW US

Minimum operations for adjacent E and E+1 pairing

C++

Java

Python3

C#

Javascript

Please Login to comment…

LEAVE A REPLY Cancel reply

Most Popular

Recent Comments

EDITOR PICKS

POPULAR POSTS

POPULAR CATEGORY

ABOUT US

FOLLOW US