Suppose there are two friends and now they want to test their friendship that how much compatible they are. Given the numbers n numbered from 1 …n and they are asked to rank the numbers. The task is find the compatibility difference between them. Compatibility difference is the number of mis-matches in the relative ranking of the same movie given by them.
Examples :
Input : a1[] = {3, 1, 2, 4, 5}
a2[] = {3, 2, 4, 1, 5}
Output : 2
Explanation : Compatibility difference is two
because first ranks movie 1 before 2 and 4 but
other ranks it after.
Input : a1[] = {5, 3, 1, 2, 4}
a2[] = {3, 1, 2, 4, 5}
Output : 5
Total difference is four due to mis-match in
position of 5
Asked in Walmart Labs
The idea is traverse both arrays.
- If current elements are same, do nothing.
- Find next position of a1[i] in a2[]. Let this position be j. One by one move a2[j] to a2[i] (Similar to bubble step of bubble sort)
Below is the implementation of above steps.
C++
// C++ program to count of misplacements#include <bits/stdc++.h>using namespace std;int findDifference(int a1[], int a2[], int n){ int res = 0; for (int i = 0; i < n; i++) { // If elements at current position // are not same if (a1[i] != a2[i]) { // Find position of a1[i] in a2[] int j = i + 1; while (a1[i] != a2[j]) j++; // Insert the element a2[j] at // a2[i] by moving all intermediate // elements one position ahead. while (j != i) { swap(a2[j], a2[j - 1]); j--; res++; } } } return res;}// Driver codeint main(){ int a1[] = { 3, 1, 2, 4, 5 }; int a2[] = { 3, 2, 4, 1, 5 }; int n = sizeof(a1)/sizeof(a1[0]); cout << findDifference(a1, a2, n); return 0;} |
Java
// Java program to count of misplacementspublic class Compatability_difference { static int findDifference(int a1[], int a2[], int n) { int res = 0; for (int i = 0; i < n; i++) { // If elements at current position // are not same if (a1[i] != a2[i]) { // Find position of a1[i] in a2[] int j = i + 1; while (a1[i] != a2[j]) j++; // Insert the element a2[j] at // a2[i] by moving all intermediate // elements one position ahead. while (j != i) { //swap int temp = a2[j - 1]; a2[j - 1] = a2[j]; a2[j] = temp; j--; res++; } } } return res; } // Driver code public static void main(String args[]) { int a1[] = { 3, 1, 2, 4, 5 }; int a2[] = { 3, 2, 4, 1, 5 }; int n = a1.length; System.out.println(findDifference(a1, a2, n)); }}// This code is contributed by Sumit Ghosh |
Python3
# Python3 program to count misplacementsdef findDifference(a1, a2, n): res = 0 for i in range(0, n): # If elements at current # position are not same if a1[i] != a2[i]: # Find position of a1[i] in a2[] j = i + 1 while (a1[i] != a2[j]): j += 1 if i >= n or j >= n: break # Insert the element a2[j] at # a2[i] by moving all intermediate # elements one position ahead. while (j != i): a2[j],a2[j-1] = a2[j-1],a2[j] res += 1 j -= 1 if i >= n or j >= n: break return res# Driver codea1 = [ 3, 1, 2, 4, 5 ]a2 = [ 3, 2, 4, 1, 5 ]n = len(a1)print(findDifference(a1, a2, n))# This code is contributed by Smitha Dinesh Semwal |
C#
// C# program to count of misplacementsusing System;public class Compatability_difference { static int findDifference(int []a1, int []a2, int n) { int res = 0; for (int i = 0; i < n; i++) { // If elements at current // position are not same if (a1[i] != a2[i]) { // Find position of a1[i] in a2[] int j = i + 1; while (a1[i] != a2[j]) j++; // Insert the element a2[j] at // a2[i] by moving all intermediate // elements one position ahead. while (j != i) { //swap int temp = a2[j - 1]; a2[j - 1] = a2[j]; a2[j] = temp; j--; res++; } } } return res; } // Driver code public static void Main() { int []a1 = {3, 1, 2, 4, 5}; int []a2 = {3, 2, 4, 1, 5}; int n = a1.Length; // Function calling Console.WriteLine(findDifference(a1, a2, n)); }}// This code is contributed by vt_m. |
Javascript
<script>// JavaScript program to count of misplacementsfunction findDifference(a1, a2, n){ let res = 0; for(let i = 0; i < n; i++) { // If elements at current position // are not same if (a1[i] != a2[i]) { // Find position of a1[i] in a2[] let j = i + 1; while (a1[i] != a2[j]) j++; // Insert the element a2[j] at // a2[i] by moving all intermediate // elements one position ahead. while (j != i) { // Swap let temp = a2[j - 1]; a2[j - 1] = a2[j]; a2[j] = temp; j--; res++; } } } return res;}// Driver codelet a1 = [ 3, 1, 2, 4, 5 ];let a2 = [ 3, 2, 4, 1, 5 ];let n = a1.length;document.write(findDifference(a1, a2, n)); // This code is contributed by sravan kumar</script> |
Output
2
This article is contributed by Rakesh Kumar. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
