Magic Elements Codechef Solution | Problem Code: ZOZ

Magic Elements Codechef Solution: You are given an array A with size N and a number K. Let’s call a position i (1 ≤ i ≤ N) valid if, after increasing A_i by K, it would be greater than the sum of all other elements in the array A.

Problem

Determine the number of distinct valid positions.

Input

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains two space-separated integers N and K.
• The second line contains N space-separated integers A₁, A₂, …, A_N.

Output

For each test case, print a single line containing one integer — the number of valid positions.

Constraints

• 1 ≤ T ≤ 100,000
• 1 ≤ N ≤ 100,000
• 1 ≤ K ≤ 10⁹
• 1 ≤ A_i ≤ 10⁴ for each valid i
• 1 ≤ sum of N over all test cases ≤ 100,000

Subtasks

Subtask #1 (33 points): sum of N over all test cases ≤ 5,000

Subtask #2 (67 points): original constraints

Sample Input 

2
4 4
2 1 6 7
4 2
2 1 5 4

Sample Output 

1

Magic Elements CodeChef Solution in CPP

#include <iostream>
using namespace std;
int solve_test()
{
    /*
    4 4
    2 1 6 7
    4 2
    2 1 5 4
    */
    int n, k;
    cin >> n >> k;
    int arr[n]; // = {2,1,6,7};
    for (int i = 0; i < n; i++) cin >> arr[i];
    int magic = 0;
    int sum;
    int incremented_value;
    for (int i = 0; i < n; i++)
    {
        incremented_value = arr[i] + k;
        sum = 0;
        for (int j = 0; j < n; j++)
        {
            if (i == j)
                continue;
            sum += arr[j];
        }
        if (incremented_value > sum)
            magic++;
    }
    return magic;
}
int main()
{
    int t = 1;
    cin >> t;
    while (t--)
        cout << solve_test() << endl;
    return 0;
}

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