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 array.
Examples:
Input : A[] = {4, 3, 2},
B[] = {7, 12, 5}
Output : 3
Explanation : A[] = {4, 3, 2} and B[] = {5, 7, 12}
results in minimum product sum. B[] = {7, 12, 5}
is 3-position different from new B[].
Input : A[] = {4, 3, 2},
B[] = { 1, 2, 3}
Output : 0
Explanation : A[] = {4, 3, 2} and B[] = {1, 2, 3}
results in minimum product sum. B[] = {1, 2, 3}
is exactly same as new one.
Idea behind finding the minimum sum of product from two array is to sort both array one in increasing and other in decreasing manner. These type of arrays will always produce minimum sum of pair product. Sorting both array will give the pair value i.e. which element from A is paired to which element from B[]. After that count the de-arrangement from original arrays.
Algorithm :
- make a copy of both array.
- sort copy_A[] in increasing, copy_B[] in decreasing order.
- Iterate for all Ai, find Ai in copy_A[] as copy_A[j] and check whether copy_B[j] == B[i] or not. Increment count if not equal.
- Return Count Value. That will be our answer.
Implementation:
CPP
// CPP program to count de-arrangements for // minimum product. #include<bits/stdc++.h> using namespace std; Â
// function for finding de-arrangement int findDearrange (int A[], int B[], int n) {  // create copy of array  vector <int> copy_A (A, A+n);  vector <int> copy_B (B, B+n);    // sort array in inc & dec way  sort(copy_A.begin(), copy_A.end());  sort(copy_B.begin(), copy_B.end(),greater<int>()); Â
 // count no. of de arrangements  int count = 0;  for (int i=0; i<n;i++)  {   vector<int>::iterator itA; Â
  // find position of A[i] in sorted array   itA = lower_bound(copy_A.begin(),       copy_A.end(), A[i]); Â
  // check whether B[i] is same as required or not   if (B[i] != copy_B[itA-copy_A.begin()])    count++;  } Â
 // return count  return count; } Â
// driver function int main() { Â int A[] = {1, 2, 3, 4}; Â int B[] = {6, 3, 4, 5}; Â int n = sizeof(A) /sizeof(A[0]);; Â cout << findDearrange(A,B,n); Â return 0; } |
Java
// Java program to count de-arrangements for// minimum product.import java.io.*;import java.util.*;Â
public class GFG {Â
  // function for finding de-arrangement  static Integer findDearrange (Integer A[], Integer B[], Integer n)  {         // create copy of array    Integer copy_A[]=A.clone();    Integer copy_B[]=B.clone();Â
    // sort array in inc & dec way    Arrays.sort(copy_A);    Arrays.sort(copy_B, Collections.reverseOrder());Â
    // count no. of de arrangements    Integer count = 0;    for (Integer i=0; i<n;i++)    {      Integer itA;Â
      // find position of A[i] in sorted array      itA = Arrays.binarySearch(copy_A, A[i]);Â
      // check whether B[i] is same as required or not      if (B[i] != copy_B[itA])        count++;    }Â
    // return count    return count;  }Â
  // driver function  public static void main (String[] args)  {    Integer A[] = {1, 2, 3, 4};    Integer B[] = {6, 3, 4, 5};    Integer n = A.length;    System.out.println(findDearrange(A,B,n));  }}Â
// This code is contributed by Pushpesh Raj. |
Python3
import copyÂ
# function for finding de-arrangementdef findDearrange(A, B, n):         # create copy of array    copy_A = copy.deepcopy(A)    copy_B = copy.deepcopy(B)Â
    # sort array in inc & dec way    copy_A.sort()    copy_B.sort(reverse=True)Â
    # count no. of de arrangements    count = 0    for i in range(n):        itA = NoneÂ
        # find position of A[i] in sorted array        itA = copy_A.index(A[i])Â
        # check whether B[i] is same as required or not        if B[i] != copy_B[itA]:            count += 1Â
    # return count    return countÂ
# driver functionA = [1, 2, 3, 4]B = [6, 3, 4, 5]n = len(A)print(findDearrange(A, B, n)) |
C#
// C# program to count de-arrangements for// minimum product.using System;Â
class GFG{    // function for finding de-arrangement    static int FindDearrange(int[] A, int[] B, int n)    {        // create copy of array        int[] copy_A = (int[])A.Clone();        int[] copy_B = (int[])B.Clone();Â
        // sort array in inc & dec way        Array.Sort(copy_A);        Array.Sort(copy_B, new Comparison<int>((a, b) => b.CompareTo(a)));Â
        // count no. of de arrangements        int count = 0;        for (int i = 0; i < n; i++)        {            // find position of A[i] in sorted array            int itA = Array.BinarySearch(copy_A, A[i]);Â
            // check whether B[i] is same as required or not            if (B[i] != copy_B[itA])                count++;        }Â
        // return count        return count;    }Â
    // Driver function    static void Main(string[] args)    {        int[] A = { 1, 2, 3, 4 };        int[] B = { 6, 3, 4, 5 };        int n = A.Length;        Console.WriteLine(FindDearrange(A, B, n));    }}Â
// This code is contributed by Aman Kumar |
Javascript
// function for finding de-arrangementfunction findDearrange(A, B, n) {    // create copy of array    const copy_A = [...A];    const copy_B = [...B];Â
    // sort array in inc & dec way    copy_A.sort((a, b) => a - b);    copy_B.sort((a, b) => b - a);Â
    // count no. of de arrangements    let count = 0;    for (let i = 0; i < n; i++) {        let itA = null;Â
        // find position of A[i] in sorted array        itA = copy_A.indexOf(A[i]);Â
        // check whether B[i] is same as required or not        if (B[i] !== copy_B[itA]) {            count += 1;        }    }Â
    // return count    return count;}Â
// driver functionconst A = [1, 2, 3, 4];const B = [6, 3, 4, 5];const n = A.length;console.log(findDearrange(A, B, n)); |
Output
2
Time Complexity: O(n 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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
