Approximately II Codechef Solution|Problem Code: APPROX2

Approximately II Codechef Solution

Problem

You are given an array of N integers a1, a2, …, aN and an integer K. Find the number of such unordered pairs {ij} that

  • i ≠ j
  • |ai + aj – K| is minimal possible

Output the minimal possible value of |ai + aj – K| (where i ≠ j) and the number of such pairs for the given array and the integer K.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case consists of two space separated integers – N and K respectively.
The second line contains N single space separated integers – a1, a2, …, aN respectively.

Output

For each test case, output a single line containing two single space separated integers – the minimal possible value of |ai + aj – K| and the number of unordered pairs {ij} for which this minimal difference is reached.

Constraints

  • 1 ≤ T ≤ 50
  • 1 ≤ ai, K ≤ 109
  • N = 2 – 31 point.
  • 2 ≤ N ≤ 1000 – 69 points.

Example

Sample Input 1 

1
4 9
4 4 2 6

Sample Output 1 

1 4

Approximately II – CodeChef Solution in JAVA

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 0; tc < T; tc++) {
			int N = sc.nextInt();
			int K = sc.nextInt();
			int[] a = new int[N];
			for (int i = 0; i < a.length; i++) {
				a[i] = sc.nextInt();
			}
			System.out.println(solve(a, K));
		}
		sc.close();
	}
	static String solve(int[] a, int K) {
		int minDiff = Integer.MAX_VALUE;
		int pairCount = 0;
		for (int i = 0; i < a.length; i++) {
			for (int j = i + 1; j < a.length; j++) {
				int diff = Math.abs(a[i] + a[j] - K);
				if (diff < minDiff) {
					minDiff = diff;
					pairCount = 1;
				} else if (diff == minDiff) {
					pairCount++;
				}
			}
		}
		return String.format("%d %d", minDiff, pairCount);
	}
}

Approximately II – CodeChef Solution in CPP

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n,k;
        cin >> n >> k;
        int ar[n];
        for(int i=0 ; i<n ; i++) cin >> ar[i];
        int minp=2e9+10;
        //cout << minp;
        for(int i=0 ; i<n-1 ; i++) {
            for(int j=i+1 ; j<n ; j++) {
                if(abs(ar[i]+ar[j]-k)<minp)
                    minp=abs(ar[i]+ar[j]-k);
            }
        }
        //cout << minp;
        int ans=0;
        for(int i=0 ; i<n-1 ; i++) {
            for(int j=i+1 ; j<n ; j++) {
                if(abs(ar[i]+ar[j]-k)==minp)
                    ans++;
            }
        }
        cout << minp << " " << ans << endl;
    }
    return 0;
}

Approximately II – CodeChef Solution in Python

T = int(input())
for i in range(T):
    n, k = map(int, input().split())
    d = list(map(int, input().split()))
    f = 0
    l = []
    for i in range(n + 1):
        for j in range(i + 1, n):
            f = abs(d[i] + d[j] - k)
            l.append(f)
    print(min(l), l.count(min(l)))

Disclaimer: The above Problem (Approximately II ) is generated by CodeChef but the solution is provided by  Chase2learn.This tutorial is only for Educational and Learning purpose.

Leave a Comment