Example: Longest Subarray Average >= K - Brute Force

// Longest Subarray Average >= K - Brute Force
#include <stdio.h>

// Function to find the longest subarray with average >= k (Brute Force)
// Time Complexity: O(N^2)
// Space Complexity: O(1)
int findLongestSubarrayBruteForce(int arr[], int n, int k) {
    // Step 1: Initialize maxLength to store the length of the longest valid subarray found
    int maxLength = 0;

    // Step 2: Iterate through all possible starting points 'i' for a subarray
    for (int i = 0; i < n; i++) {
        long long currentSum = 0; // Use long long to prevent potential overflow for sum

        // Step 3: Iterate through all possible ending points 'j' for the subarray starting at 'i'
        for (int j = i; j < n; j++) {
            currentSum += arr[j]; // Add current element to the sum
            int currentLength = j - i + 1; // Calculate the current subarray length

            // Step 4: Check if the average of the current subarray is >= k
            // currentSum / currentLength >= k  is equivalent to  currentSum >= k * currentLength
            // Multiply k by currentLength first to avoid floating point arithmetic and maintain precision
            if (currentSum >= (long long)k * currentLength) {
                // If the condition is met, update maxLength if currentLength is greater
                if (currentLength > maxLength) {
                    maxLength = currentLength;
                }
            }
        }
    }
    return maxLength;
}

int main() {
    // Sample Output for Approach 1

    // Example 1
    int arr1[] = {1, 2, 3, 4, 5};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int k1 = 3;
    printf("Array: {1, 2, 3, 4, 5}, k = 3\n");
    printf("Longest subarray length (Brute Force): %d\n", findLongestSubarrayBruteForce(arr1, n1, k1));

    // Example 2
    int arr2[] = {2, 1, 4, 3, 5};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    int k2 = 3;
    printf("\nArray: {2, 1, 4, 3, 5}, k = 3\n");
    printf("Longest subarray length (Brute Force): %d\n", findLongestSubarrayBruteForce(arr2, n2, k2));

    // Example 3
    int arr3[] = {10, 20, 30, 40};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    int k3 = 25;
    printf("\nArray: {10, 20, 30, 40}, k = 25\n");
    printf("Longest subarray length (Brute Force): %d\n", findLongestSubarrayBruteForce(arr3, n3, k3));

    // Example 4: No such subarray
    int arr4[] = {1, 2, 0, 1};
    int n4 = sizeof(arr4) / sizeof(arr4[0]);
    int k4 = 5;
    printf("\nArray: {1, 2, 0, 1}, k = 5\n");
    printf("Longest subarray length (Brute Force): %d\n", findLongestSubarrayBruteForce(arr4, n4, k4));
    
    return 0;
}