Horje
Minimum operations for adjacent E and E+1 pairing

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

1

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


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Permutations of an Array in lexicographical order. Permutations of an Array in lexicographical order.
C++ Multidimensional Array C++ Multidimensional Array
Minimum operations for same MEX Minimum operations for same MEX
Shift the elements between two arrays in Z form Shift the elements between two arrays in Z form
Searching Elements in an Array | Array Operations Searching Elements in an Array | Array Operations

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 15



 

Horje