fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. // AtMost(K) -> finding the number of subarrays
  6. // whose sum is less than or equal to K
  7. int atMost(int a[], int n, int k)
  8. {
  9.     int cnt = 0;
  10.     int sum = 0;
  11.  
  12.     int i = 0, j = 0;
  13.  
  14.     while (j < n)
  15.     {
  16.         // Do calculation:
  17.         // Add the current j index element to the window
  18.         sum = sum + a[j];
  19.  
  20.         // If the current window sum is <= k
  21.         if (sum <= k)
  22.         {
  23.             // All subarrays ending at j and starting
  24.             // from i, i+1, ..., j have sum <= k.
  25.             // Number of such subarrays = j-i+1
  26.             cnt = cnt + (j - i + 1);
  27.  
  28.             // Move j forward to explore the next element
  29.             j++;
  30.         }
  31.         else if (sum > k)
  32.         {
  33.             // Shrink the window until sum <= k
  34.             while (i <= j && sum > k)
  35.             {
  36.                 // Remove the element at index i
  37.                 sum = sum - a[i];
  38.  
  39.                 // Move i forward
  40.                 i++;
  41.             }
  42.  
  43.             // After shrinking, if sum <= k,
  44.             // we have a valid window ending at j.
  45.             if (sum <= k)
  46.             {
  47.                 // Count all valid subarrays ending at j
  48.                 cnt = cnt + (j - i + 1);
  49.  
  50.                 // Move j forward
  51.                 j++;
  52.             }
  53.         }
  54.     }
  55.  
  56.     return cnt;
  57. }
  58.  
  59. int main()
  60. {
  61.     int n = 5;
  62.     int a[] = {1, 11, 2, 3, 15};
  63.  
  64.     int k = 10;
  65.  
  66.     // Number of subarrays with sum <= k
  67.     int atK = atMost(a, n, k);
  68.  
  69.     // Number of subarrays with sum <= k-1
  70.     int atKminus1 = atMost(a, n, k - 1);
  71.  
  72.     // Exact K = AtMost(K) - AtMost(K-1)
  73.     int ans = atK - atKminus1;
  74.  
  75.     cout << ans << endl;
  76.  
  77.     return 0;
  78. }
  79.  
  80. /*
  81. important point: our current code has special conditions for sum != 0 and sum == 0. We don't need those conditions in the standard atMost() logic. We can simplify the code while preserving your pointer-based approach.
  82.  
  83. Suppose we want subarrays with sum exactly K = 10.
  84. - AtMost(10) counts every subarray whose sum is at most 10.
  85. - AtMost(9) counts every subarray whose sum is at most 9.
  86. - Subtracting removes all the subarrays with sum less than 10.
  87. */
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/VbtnoX
language:
C++ (gcc 8.3)
created:
8 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!