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 ≤ Nvalid if, after increasing Ai by K, it would be greater than the sum of all other elements in the array A.

Magic Elements Codechef Solution

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 A1, A2, …, AN.

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 ≤ 109
  • 1 ≤ Ai ≤ 104 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.

Leave a Comment