Given three numbers x y and z define distance x y z max lx

Given three numbers, x, y, and z, define distance (x, y, z) = max (lx - y|, |x - z|, |y - z|) Design an algorithm that takes three sorted arrays A, B, C of integers and returns a triple (A[i], B[j], C[k]) such that the distance (A[i], B[j], C[k] is minimum. Your algorithm should run in O(n_A + n_B + n_C) where n_A is the length of A, n_B is the length of B and n_C is the length of C.

Solution

Solution:-

Given three sorted arrays A[], B[] and C[],we have to find 3 elements i, j and k from A, B and C respectively such that max(|A[i] – B[j]|, |B[j] – C[k]|, |C[k] – A[i])| is minimized.

Efficient Solution Let ‘p’ be size of A[], ‘q’ be size of B[] and ‘r’ be size of C[]

Note that we increment the pointer of the array which has the minimum, because our goal is to decrease the difference. Increasing the maximum pointer increases the difference. Increase the second maximum pointer can potentially increase the difference.

C++ program to find 3 elements such that max(abs(A[i]-B[j]), abs(B[j]-C[k]), abs(C[k]-A[i])) is minimized.

#include<bits/stdc++.h>

using namespace std;

void findClosest(int A[], int B[], int C[], int p, int q, int r)

{

    int diff = INT_MAX; // Initialize min diff

    // Initialize result

    int res_i =0, res_j = 0, res_k = 0;

    // Traverse arrays

    int i=0,j=0,k=0;

    while (i < p && j < q && k < r)

    {

        // Find minimum and maximum of current three elements

        int minimum = min(A[i], min(B[j], C[k]));

        int maximum = max(A[i], max(B[j], C[k]));

        // Update result if current diff is less than the min

        // diff so far

        if (maximum-minimum < diff)

        {

             res_i = i, res_j = j, res_k = k;

             diff = maximum - minimum;

        }

        // We can\'t get less than 0 as values are absolute

        if (diff == 0) break;

        // Increment index of array with smallest value

        if (A[i] == minimum) i++;

        else if (B[j] == minimum) j++;

        else k++;

    }

    // Print result

    cout << A[res_i] << \" \" << B[res_j] << \" \" << C[res_k];

}

// Driver program

int main()

{

    int A[] = {1, 4, 10};

    int B[] = {2, 15, 20};

    int C[] = {10, 12};

    int p = sizeof A / sizeof A[0];

    int q = sizeof B / sizeof B[0];

    int r = sizeof C / sizeof C[0];

    findClosest(A, B, C, p, q, r);

    return 0;

}

Output: