Linkedin | Coding OA and Solutions | Set-30| 2026 | DSA round | Software Engineer

Question

Answer 1

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int[] distance = {50, 55, 60};
        int[] targetDistance = {60, 55, 50, 65};  

        int[] result = countMinOperations(distance, targetDistance);

        System.out.println("Result: " + Arrays.toString(result));
    }

    public static int[] countMinOperations(int[] dist, int[] target) {
        int n = dist.length;
        int q = target.length;
        Arrays.sort(dist);
        
        long[] ps = new long[n + 1];
        for(int i = 0; i < n; i++) {
            ps[i + 1] = ps[i] + dist[i];
        }
        
        int[] ans = new int[q];
        for(int i = 0; i < q; i++) {
            long x = target[i];
            int idx = lowerBound(dist, target[i]);
            
            long leftSum = ps[idx];
            long leftCnt = idx;
            long leftTotal = (x * leftCnt) - leftSum;
            
            long rightSum = ps[n] - ps[idx];
            long rightCount = (n - idx);
            long rightTotal = rightSum - (x * rightCount);
            
            ans[i] = (int)(leftTotal + rightTotal);
        }
        
        return ans;
    }

    public static int lowerBound(int[] dist, int target) {
        int low = 0;
        int high = dist.length - 1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(dist[mid] >= target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}