Example: Longest Subarray Average >= K - Binary Search on Answer

// Longest Subarray Average >= K - Binary Search on Answer
#include <stdio.h>
#include <stdbool.h> // For bool type
#include <limits.h>  // For INT_MIN/MAX

// Helper function to check if there is any subarray of a given 'length'
// whose average is greater than or equal to k.
// Time Complexity: O(N)
bool check(int arr[], int n, int k, int length) {
    if (length == 0) return true; // An empty subarray technically has an average >= k
                                  // (or is not considered for a positive length problem)
                                  // For finding positive length, this effectively means we found a valid length.
    if (length > n) return false;

    long long currentSum = 0;
    // Step 1: Calculate sum for the first window of 'length'
    for (int i = 0; i < length; i++) {
        currentSum += arr[i];
    }

    // Step 2: Check the first window
    if (currentSum >= (long long)k * length) {
        return true;
    }

    // Step 3: Use a sliding window to check subsequent subarrays of 'length'
    for (int i = length; i < n; i++) {
        currentSum += arr[i] - arr[i - length]; // Slide window: add new element, remove old
        if (currentSum >= (long long)k * length) {
            return true;
        }
    }

    return false; // No subarray of 'length' found with average >= k
}


// Function to find the longest subarray with average >= k using Binary Search on Answer
// Time Complexity: O(N log N) (N for check function, log N for binary search)
// Space Complexity: O(1)
int findLongestSubarrayBinarySearch(int arr[], int n, int k) {
    // Step 1: Define the search space for the length of the subarray
    // The length can be from 0 (if no such subarray, or for edge cases) to n
    int low = 0;
    int high = n;
    int ans = 0; // Stores the maximum valid length found

    // Step 2: Perform binary search on the possible lengths
    while (low <= high) {
        int mid = low + (high - low) / 2; // Calculate the middle length

        // Step 3: Use the helper 'check' function to see if 'mid' length is possible
        if (check(arr, n, k, mid)) {
            // If a subarray of 'mid' length exists with average >= k,
            // then 'mid' is a possible answer. We try to find an even longer one.
            ans = mid;
            low = mid + 1;
        } else {
            // If no subarray of 'mid' length satisfies the condition,
            // then we need to look for shorter lengths.
            high = mid - 1;
        }
    }

    return ans; // 'ans' will hold the longest possible length
}

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

    // 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 (Binary Search): %d\n", findLongestSubarrayBinarySearch(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 (Binary Search): %d\n", findLongestSubarrayBinarySearch(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 (Binary Search): %d\n", findLongestSubarrayBinarySearch(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 (Binary Search): %d\n", findLongestSubarrayBinarySearch(arr4, n4, k4));
    
    return 0;
}