Hello coders, today we are going to solve Approximately II Codechef Solution|Problem Code: APPROX2.
Problem
You are given an array of N integers a1, a2, …, aN and an integer K. Find the number of such unordered pairs {i, j} 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 {i, j} 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 6Sample Output 1
1 4Approximately 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.