medium
1 views

Four Players Score Combination

Count the number of combinations of exactly 4 players whose total runs scored is greater than or equal to 100.

Understand the Problem

Problem Statement

Four Players Score Combination: The program must accept the score of N players in a cricket match. The program must print the number of combinations with exactly 4 players and total runs scored by the 4 players is greater than or equal to 100 as the output.

Constraints

  • The number of players N is between 4 and 250 (inclusive)
  • Each player's score is a non-negative integer
  • We need to find all combinations of exactly 4 players
  • Order of players in a combination does not matter
  • We count combinations where the sum of scores is >= 100

Examples

Example 1
Input
6
20 50 20 10 30 25
Output
10
Explanation

From 6 players with scores [20, 50, 20, 10, 30, 25], there are C(6,4) = 15 total combinations. Out of these, 10 combinations have a total score >= 100. For example: (50,20,30,25) = 125, (50,20,30,20) = 120, etc.

Example 2
Input
8
32 11 40 60 26 23 66 43
Output
69
Explanation

From 8 players with scores [32, 11, 40, 60, 26, 23, 66, 43], there are C(8,4) = 70 total combinations. Out of these, 69 combinations have a total score >= 100. Only one combination has a sum less than 100.

Solution

#include <stdio.h>
#include <stdlib.h>

// Function to calculate combination count using recursion
void countCombinations(int arr[], int n, int index, int data[], int i, int k, int *count, int target) {
    // Base case: if we have selected k elements
    if (index == k) {
        int sum = 0;
        for (int j = 0; j < k; j++) {
            sum += data[j];
        }
        if (sum >= target) {
            (*count)++;
        }
        return;
    }

    // If no more elements are there
    if (i >= n) {
        return;
    }

    // Include current element
    data[index] = arr[i];
    countCombinations(arr, n, index + 1, data, i + 1, k, count, target);

    // Exclude current element
    countCombinations(arr, n, index, data, i + 1, k, count, target);
}

int main() {
    int n;
    scanf("%d", &n);

    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    int k = 4;
    int target = 100;
    int count = 0;
    int data[k];

    countCombinations(arr, n, 0, data, 0, k, &count, target);

    printf("%d\n", count);

    return 0;
}
Time:O(C(N,4)) = O(N^4/24) ≈ O(N^4)
Space:O(4) = O(1) for the recursion stack depth and data array
Approach:

C Solution Explanation:

  1. Read the number of players N and their scores into an array
  2. Use a recursive function countCombinations to generate all possible combinations of 4 players
  3. The recursive function works by either including or excluding each player
  4. When we have selected exactly 4 players (index == k), calculate their sum
  5. If sum >= 100, increment the count
  6. The recursion explores all C(N,4) possible combinations
  7. Finally, print the total count of valid combinations

Visual Explanation

Loading diagram...
All Problems