Minimize the number of swaps [wrong example] [awaiting]

By Ann Roberts On Jan 30, 2023

Given two arrays X[] and Y[] of length N along with an integer C. Return the minimum possible cost of operations by optimally arranging X[] and Y[] where we can choose the leftmost element of Y[] (Until Y[] becomes empty )let’s say A and place it at beginning of X[] and then swap it to the right in X[] until A is smaller than its right element. Each swap is counted as one operation having a cost C.

Examples:

Input: N = 5 ,M = 3, C = 4, X[] = {10, 5, 2, 5, 4}, Y[] = {3, 1, 2}
Output: 20
Explanation: Optimal arrangement can be: X[]={2, 10, 5, 4, 5} and Y[]={1, 2, 3}

First operation: Put Y[1]=1 at the start of X[], Then X[]={ 1, 2, 10, 5, 4, 5}, No swaps are needed.

Second operation: Put Y[2]=2 at the starting of X[], Then X[]={ 2, 1, 2, 10, 5, 4, 5}, After that perform two swaps on element 2 in X[]={1, 2, 2, 10, 5, 4, 5}.

Third operation: Put Y[3]=3 at the starting of X[], Then X[]={ 3 1, 2, 2, 10, 5, 4, 5}, After three swaps X[]= {1, 2, 2, 3, 10, 5, 4, 5}

Total swaps=2+3=5, the total cost is 5*4=20. It can be verified that it is the minimum possible cost such that all elements of Y[] will be in sorted order with respect to X[] by following the given operation.

Input: N = 3 ,M = 2, C = 5, X[] = {4, 3, 5}, Y[] = {4, 1}
Output: 15
Explanation: It can be verified that the minimum cost will be 15 for the optimal arrangement of X[] and Y[].

Approach: Implement the idea below to solve the problem:

The problem is based on sorting and can be solved by using some observations.

Steps were taken to solve the problem:

Sort X[] and Y[].
Create a variable let’s say operation and initialize it equal to zero.
Run a loop for i=0 to less than m and follow the below-mentioned steps under the scope of the loop:
- if (arr2[i] < arr1[0]), then operations += n else continue
Print the value of operations*cost.

Below is the code to implement the above approach:

Java

import java.io.*;

import java.lang.*;

import java.util.*;

class GFG {

public static void main(String[] args)

{

long n = 5;

long m = 3;

long cost = 5;

long arr1[] = { 10, 5, 2, 5, 4 };

long arr2[] = { 3, 1, 2 };

min_cost(n, m, arr1, arr2, cost);

}

static void min_cost(long n, long m, long[] arr1,

long[] arr2, long cost)

{

Arrays.sort(arr1);

Arrays.sort(arr2);

long operations = 0;

for (int i = 0; i < m; i++) {

if (arr2[i] < arr1[0])

operations += n;

else

continue;

}

System.out.println(operations * cost);

}

Time Complexity: O(N*Log(N))
Auxiliary Space: O(1)