C Online Compiler
Example: Longest Subarray Average >= K - Brute Force
C
C++
C#
Java
Python
PHP
main.c
STDIN
Run
// Longest Subarray Average >= K - Brute Force #include
// 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; }
Output
Clear
ADVERTISEMENTS