Given an array of integers arr and two integers k and threshold.
Return the number of sub-arrays of size k and average greater than or equal to threshold.
 
Example 1:
Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).

Example 2:
Input: arr = [1,1,1,1,1], k = 1, threshold = 0
Output: 5

Example 3:
Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output: 6
Explanation: The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers.

Example 4:
Input: arr = [7,7,7,7,7,7,7], k = 7, threshold = 7
Output: 1

Example 5:
Input: arr = [4,4,4,4], k = 4, threshold = 1
Output: 1

 
Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^4
1 <= k <= arr.length
0 <= threshold <= 10^4

Difficulty: interview

Starter code:

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        

Solutions:
class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        if len(arr) < k:
            return 0
        bar = k * threshold
        total = 0
        window = sum(arr[:k])
        if window >= bar:
            total += 1
        for i in range(k, len(arr)):
            window -= arr[i - k]
            window += arr[i]
            if window >= bar:
                total += 1
        return total

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        s = threshold*k
        s1 = sum(arr[:k])
        n = len(arr)
        c = 0
        if s1>=s:
            c+=1
        for i in range(k,n):
            s1 -= arr[i-k]
            s1 += arr[i]
            if s1>=s:
                c+=1
        return c

class Solution:
    def numOfSubarrays(self, nums: List[int], k: int, target: int) -> int:
        target *= k
        ans = 0
        summ = 0
        for i,n in enumerate(nums):
            if i >= k:
                summ -= nums[i - k]
                
            summ += n
            
            if i >= k - 1:
                if summ >= target:
                    ans += 1
        return ans

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        # sliding window
        minVal = k * threshold
        
        beg = 0
        end = k - 1
        total = 0
        currSum = 0
        
        for i in range(beg, end+1):
            currSum += arr[i]

        while end < len(arr):
            if beg != 0:
                currSum = currSum - arr[beg - 1] + arr[end] 
            
            if currSum >= minVal:
                total+= 1
            beg += 1
            end += 1
            
        return total

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        # subarry, not sub elements, can be resolved by using running sum
        
        cur = 0
        res = 0
        for i in range(k):
            cur += arr[i]
        if cur / k >= threshold:
            res += 1
        for i in range(k, len(arr)):
            cur = cur + arr[i] - arr[i - k]
            if cur / k >= threshold:
                res += 1
        return res

class Solution:
    def numOfSubarrays(self, a: List[int], k: int, threshold: int) -> int:
        prefixSum = [0]
        for i in a:
            prefixSum.append(i + prefixSum[-1])
        return sum(prefixSum[i + k] - prefixSum[i] >= k * threshold for i in range(len(a) - k + 1))


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        start = 0
        end = k

        count = 0

        #Sum the values initially as a buffer
        sumInit = sum(arr[start:end])                                   

        #To check if the average exceeds threshold if yes increase count by 1
        if ((sumInit / k) >= threshold):                                
            count += 1

        #To check end is within limits
        while end < len(arr):   
            #Subtract the start and end
            sumInit = sumInit - arr[start] + arr[end]
            #Check if average exceeds threshold
            if ((sumInit / k) >= threshold):
                count += 1
            start += 1
            end += 1



        return count

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        if len(arr) < k:
            return 0
        
        prevAverage = 0
        counter = 0
        for i in range(len(arr)-k+1):
            if i == 0:
                average = sum(arr[i:i+k])/k
            else:
                average = (prevAverage*k - (arr[i-1]) + arr[i+k-1])/k
                
            if average >= threshold:
                counter+=1
                
            #print(arr[i:i+k], prevAverage, average)
                
            prevAverage = average
            
        return counter

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        start = 0
        count = 0
        threshold = threshold * k
        avg = sum(arr[start:k])
        i = k
        while i <= len(arr):
            if start != 0:
                avg = avg - arr[start-1] + arr[i-1]
            if avg >= threshold:
                count += 1
                start += 1
                i = start + k
            else:
                start += 1
                i += 1
        
        return count
        
        
        


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        i, j = 0, k-1
        total = sum(arr[i: j+1])
        target = threshold * k
        res = 0
        if total >= target:
            res += 1
        while j < len(arr) - 1:
            total -= arr[i]
            i += 1
            j += 1
            total += arr[j]
            if total >= target:
                res += 1
        return res


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        dp=[0]*len(arr)
        dp[0]=arr[0]
        for i in range(1,len(arr)):
            dp[i]=dp[i-1]+arr[i]
        cn=0
        for i in range(k-1,len(arr)):
            if i==k-1:
                if dp[i]//k>=threshold:
                    cn+=1
            else:
                if (dp[i]-dp[i-k])//k>=threshold:
                    cn+=1
        return cn

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        target = k * threshold
        curr_sum = sum(arr[:k])
        res = 1 if curr_sum >= target else 0
        
        for i in range(k, len(arr)):
            curr_sum = curr_sum - arr[i - k] + arr[i]
            if curr_sum >= target:
                res += 1
        
        return res


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        c=0
        a=0
        f=0
        for i in range(len(arr)):
            a=a+1
            c=c+arr[i]
            if a>=k:
                if c/k>=threshold:
                    f=f+1
                c=c-arr[i-a+1]
                a=a-1
        return f            
                    


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        
        size = len(arr)
        
        avg = sum(arr[:k]) / k
        count = 1 if avg >= threshold else 0
        
        end = k
        
        while end < size:
            prevVal = arr[end-k] / k
            nextVal = arr[end] / k
            
            avg += nextVal - prevVal
            
            count += 1 if avg >= threshold else 0
            end += 1
            
        return count
        


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        total = sum(arr[:k])
        result = 0
        for i in range(k, len(arr) + 1):
            avg = total / k
            if avg >= threshold:
                result += 1
            
            if i < len(arr):
                left = arr[i-k]
                right = arr[i]
                total -= left
                total += right
        
        return result


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, t: int) -> int:
        cur = 0
        ans = 0
        for i in range(len(arr)):
            cur += arr[i]
            if i>=k:
                cur -= arr[i-k]
            if i>=k-1 and cur >= k*t:
                ans += 1
        return ans
                


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        
        presum = [0]
        
        for num in arr:
            presum.append( presum[-1]+num )
        
        res = 0
        i=0
        while i+k < len(presum):
            if presum[i+k]-presum[i] >= threshold*k:
                res += 1
            i+= 1
        
        return res

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        c=0
        a=0
        f=0
        for i in range(len(arr)):
            a=a+1
            c=c+arr[i]
            while a>=k:
                if c/k>=threshold:
                    f=f+1
                c=c-arr[i-a+1]
                a=a-1
        return f            
                    


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        ans, sm = 0, 0
        q = deque()
        
        for v in arr:
            sm += v
            q.append(v)
            
            if len(q) > k:
                sm -= q.popleft()
            
            if len(q) == k:
                ans += ((sm/k) >= threshold)
        
        return ans

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        n = len(arr)
        target = threshold * k
        n_subarrays = n - k + 1
        
        curr_sum = sum(arr[0:k])
        count    = 0 if (curr_sum < target) else 1

        for i in range(1, n_subarrays):
            curr_sum += (-arr[i-1] + arr[i+k-1])
            count = count if (curr_sum < target) else (count + 1)
            
        return count


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        if not arr or len(arr) < k:
            return 0
        
        summ = [0]
        res = 0 
        for p, v in enumerate(arr):
            i = p+1  
            summ.append(summ[p] + v)
            if i-k >= 0:
                if (summ[i] - summ[i-k]) / k >= threshold:
                    res +=1 
        
        return res
            
            


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        rep=0
        target=k*threshold
        
        cur=sum(arr[:k])
        if cur>=target:
            rep+=1
        l,r=0,k
        while r<len(arr):
            cur-=arr[l]
            cur+=arr[r]
            l+=1
            r+=1
            if cur>=target:
                rep+=1
        return rep

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        
        answer = 0
        
        initial_sum = sum(arr[:k])
        
        for i in range(len(arr) - k + 1):
            if i == 0:
                if initial_sum / k >= threshold:
                    answer += 1
            else:
                initial_sum = initial_sum - arr[i - 1] + arr[i + k - 1]
                if initial_sum / k >= threshold:
                    answer += 1
                
        return answer

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        threshold *= k
        window = 0
        ans = 0
        for r, num in enumerate(arr):
            window += num
            if r >= k:
                window -= arr[r - k]
            if r >= k - 1 and window >= threshold:
                ans += 1
        return ans

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        ans = 0
        
        n = len(arr)
        start = 0
        end = 0
        
        presum = [0]
        
        for num in arr:
            presum.append(presum[-1]+num)
        
        for i in range(0,n-k+1):
            
            
            if (presum[i+k]-presum[i]) / k >= threshold:
                # print(arr[start:end])
                ans += 1
        
            
        return ans
            
            


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        #### Sliding window problem
        
        ### Edge case
        if len(arr) < k: return None
        
        ###Initialize variables and this is required to initilize the first condition as in the while loop
        ### k_sum = k_sum - arr[p1] + arr[p2] already take to next k+1 calculation
        k_sum = sum([arr[i] for i in range(0,k)])
        count = 0
        p1, p2 = 0, k
        
        if k_sum/k >= threshold: count+= 1
        
        while p2 < len(arr):

            k_sum = k_sum - arr[p1] + arr[p2]
                
            if k_sum/k >= threshold: count+= 1

        
        
            p1 += 1
            p2 += 1
        
        return count
        
        
        
    
        
        
#         ## Backtacking time out!
#         res = []
        
#         def helper(start_pos = 0, curr_arr = []):
#             if len(curr_arr) == k and mean(curr_arr) >= threshold:
#                 res.append(curr_arr[:])
#             elif len(curr_arr) == k:
#                 return
#             else:
#                 curr_arr.append(arr[start_pos])
                
#                 helper(start_pos = start_pos + 1, curr_arr = curr_arr)
                
#                 curr_arr.pop()
        
        
#         for i in range(len(arr) - k + 1):
#             helper(start_pos = i, curr_arr = [])
        
#         return len(res)


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        sm = threshold * k
        ct = 0
        tot = 0
        for i in range(len(arr)):
            tot += arr[i]
            if i < k - 1: continue
            if i > k - 1: tot -= arr[i - k]
            if tot >= sm: ct += 1
        return ct
            


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        n=len(arr)
        a=[0]*(n+1)
        for i in range(1,n+1):
            a[i]=arr[i-1]+a[i-1]
        cnt=0
        for i in range(k,n+1):
            res=a[i]-a[i-k]
            if(res/k>=threshold):
                cnt+=1
        return cnt
            


class Solution:
    def __init__(self):
        self.counter = 0
        self.threshold = 0
        self.k = 0

    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        self.k = k
        self.threshold = threshold

        interval = sum(arr[:k])
        self._count_if_slice_sum_passes_threshold(interval)

        left = 0
        while left + k < len(arr):
            interval -= arr[left]
            left += 1
            right = left + k - 1
            interval += arr[right]
            self._count_if_slice_sum_passes_threshold(interval)
        return self.counter

    def _count_if_slice_sum_passes_threshold(self, slice):
        if slice / self.k >= self.threshold:
            self.counter += 1

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        temp = sum(arr[:k])
        count = 0 if temp / k < threshold else 1
        
        for i in range(k, len(arr)):
            temp = temp - arr[i - k] + arr[i]
            if temp / k >= threshold:
                count += 1
            
        
        return count

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        s = l = 0
        for r in range(k):
            s += arr[r]
        ans = 0
        while(r < len(arr)-1):
            if(s >= threshold*k):
                ans += 1
            s -= arr[l]
            l += 1
            r += 1
            s += arr[r]
        ans += (s >= threshold*k)
        return ans

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        if k > len(arr):
            return 0
        
        min_sum = k * threshold
        
        # first sum!
        running_sum = sum(arr[0:k])
        
        if running_sum >= min_sum:
            count = 1
        else:
            count = 0
        
        for i in range(len(arr) - k):
            running_sum -= arr[i]
            running_sum += arr[i + k]
            if running_sum >= min_sum:
                count += 1
            
        return count


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        ans = 0
        x = 0
        running_sum = sum(arr[0:k])
        if running_sum/k >= threshold: ans+=1
        for x in range(len(arr)-k):
            running_sum+=arr[k+x]-arr[x]
            if running_sum/k >= threshold: ans+=1
        return ans


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        averages = []
        first = True
        sum_avg = 0
        for i in range(len(arr) - (k - 1)):
            if first:
                for j in range(k):
                    sum_avg += arr[i + j]
                first = False
            else:
                sum_avg -= arr[i - 1]
                sum_avg += arr[i + (k - 1)]
            averages.append(sum_avg / k)
        averages.sort(reverse=True)
        i = 0
        while i < len(averages) and averages[i] >= threshold:
            i += 1
        return i

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        l,r = 0,k-1
        temp = 0
        for i in range(l, r+1):
            temp += arr[i]
        res = 0 if temp<k*threshold else 1
        while r<len(arr)-1:
            temp += arr[r+1]-arr[l]
            r += 1
            l += 1
            if temp >= k*threshold:
                res += 1
        return res


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        for i in range(1,len(arr)):
            arr[i]+=arr[i-1]
        counter=0
        for i in range(len(arr)):
            if i-k>=0:
                if (arr[i]-arr[i-k])/k>=threshold:
                    counter+=1
            elif i-k==-1:
                if arr[i]/k>=threshold:
                    counter+=1
        return counter


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        l = 0
        r = k - 1
        total = sum(arr[0:k])
        if total/k >= threshold:
            count = 1
        else:
            count = 0
        
        while r < len(arr) - 1:
            total -= arr[l]
            l += 1
            r += 1
            total += arr[r]
            if total/k >= threshold:
                count += 1
        
        return count
            


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        i=0
        j=i+k
        s=sum(arr[i:j])
        c=0
        while(j<=len(arr)):
            if(s//k>=threshold):
                #print(s,arr[i:j])
                c+=1
            s-=arr[i]
            if(j<len(arr)):
                s+=arr[j]
            j+=1
            i+=1
        return c

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        ans = 0
        total = 0
        if len(arr) < k:
            return 0
        else:
            for i in range(k):
                total += arr[i]
            if float(total/k) >= threshold:
                ans += 1    
                
            i = k
            while i < len(arr):                
                total += arr[i] - arr[i-k]
                if float(total/k) >= threshold:
                    ans += 1
                i += 1
            return ans

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        if len(arr)<k:
            return 0
        store=[0]*len(arr)
        i=0
        j=0
        ans=0
        while i<len(arr):
            if i-j+1==k:
                if j==0:
                    store[i]=store[i-1]+arr[i]
                else:
                    store[i]=store[i-1]+arr[i]-arr[j-1]
                if store[i]//k>=threshold:
                    ans=ans+1
                j=j+1
                i=i+1
            else:
                if i==0:
                    store[i]=arr[i]
                else:
                    store[i]=arr[i]+store[i-1]
                i=i+1
        return ans

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        goal = k * threshold
        cSums = [0 for i in arr]
        c = 0
        for i in range(len(arr)):
            if i == 0:
                cSums[0] = arr[0]
            else:
                cSums[i] = cSums[i-1] + arr[i]
            if i == k-1:
                if cSums[i] >= goal:
                    c += 1
            elif i >= k:
                if cSums[i] - cSums[i-k] >= goal:
                    c += 1
        print(cSums)
        return c

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        sumThreshold = k*threshold
        arrLength = len(arr)
        currentSum = 0##be sure you always define local variables before calling them...
        for i in range(k):
            currentSum += arr[i]
        count = 0
        if currentSum >= sumThreshold:
            count += 1
        for i in range(k,arrLength):
            currentSum += arr[i]-arr[i-k]
            if currentSum >= sumThreshold:
                count += 1
        return count


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        # establish the first sum
        s = 0
        ret = 0
        for i, num in enumerate(arr):
            if i - k < 0:
                s += num
                if s >= threshold * k and i == k-1:
                    ret += 1
                    print(i)
                continue
            s -= arr[i-k]
            s += num
            if s >= threshold * k:
                ret += 1
                print(i)
        return ret


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        s=0
        c=0
        for i in range(k):
            s=s+arr[i]
        if(s/k>=threshold):
            c=c+1
        for i in range(k,len(arr)):
            s=s+arr[i]
            s=s-arr[i-k]
            if(s/k>=threshold):
                c=c+1
        return c
        
                


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        
        output = 0
    
        #calculate initial sum
        summ = 0
        for i in range(k):
            summ += arr[i]

        #check initial summ for avg
        if summ / k >= threshold:
            output += 1

        for i in range(k, len(arr)):
            summ = summ + arr[i] - arr[i-k]
            if summ / k >= threshold:
                output += 1

        return output

class Solution:
    def numOfSubarrays(self, a: List[int], k: int, threshold: int) -> int:
        lo, sum_of_win, cnt, target = -1, 0, 0, k * threshold
        for hi, v in enumerate(a):
            sum_of_win += v
            if hi - lo == k:
                if sum_of_win >= target:
                    cnt += 1
                lo += 1   
                sum_of_win -= a[lo]
        return cnt


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        res = 0
        s = sum(arr[:k-1])
        t = threshold * k
        for i in range(k - 1, len(arr)):
            s += arr[i]
            if s >= t:
                res += 1
            s -= arr[i+1-k]
        return res

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        target = k * threshold
        s, ans = 0, 0
        for i, num in enumerate(arr):
            if i < k:
                s += num
                continue
            if s >= target:
                ans += 1  
            s = s - arr[i - k] + arr[i]
        if s >= target:
            ans += 1
        return ans

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        tmp = [sum(arr[:k])]
        
        for i in range(k, len(arr)):
            temp = tmp[-1]
            temp = temp - arr[i - k] + arr[i]
            tmp.append(temp)
            
        print(tmp)
        
        count = 0
        
        for el in tmp:
            if el / k >= threshold:
                count += 1
        
        return count

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        p = k - 1
        res = 0
        s = sum(arr[:k-1])
        t = threshold * k
        for i in range(k - 1, len(arr)):
            s += arr[i]
            if s >= t:
                res += 1
            s -= arr[i+1-k]
        return res

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        threshold*=k
        n = len(arr)
        l=0
        tmp_sum=0
        count=0
        for i in range(k):
            tmp_sum+=arr[i]
        if tmp_sum>=threshold:
            count+=1
        for l in range(n-k):
            tmp_sum-=arr[l]
            r=l+k
            tmp_sum+=arr[r]
            if tmp_sum>=threshold:
                count+=1
        return count


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        l = len(arr)
        ans = 0
        x = 0
        running_sum = sum(arr[0:k])
        if running_sum/k >= threshold: ans+=1
        while k+x < l:            
            running_sum+=arr[k+x]-arr[x]
            if running_sum/k >= threshold: ans+=1
            x+=1
        return ans


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        ans = 0
        total = 0
        threshold = k*threshold
        if len(arr) < k:
            return 0
        else:
            #check the first k numbers
            for i in range(k):
                total += arr[i]
            if total >= threshold:
                ans += 1    
            
            #slide window to the right 1
            i = k
            while i < len(arr):                
                total += arr[i] - arr[i-k]
                if total >= threshold:
                    ans += 1
                i += 1
            return ans

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        run = [0]
        for i in range(len(arr)):
            run.append(run[-1] + arr[i])
        res = 0
        for i in range(k, len(arr) + 1):
            if (run[i] - run[i - k]) / k >= threshold:
                res += 1
        return res

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        curr = sum(arr[:k])
        ans = 1 if curr >= threshold*k else 0
        for i in range(k, len(arr)):
            curr += arr[i]
            curr -= arr[i-k]
            # print(curr)
            if curr >= threshold*k:
                ans += 1
        return ans
            


class Solution:
    def numOfSubarrays(self, A, k, target):     
        # NOTE:
        #     - Since avg = sum/k , and \"k\" is fixed, we can work with the (minimum) \"sum\" directly 
        #     - So we can multiple \"target\" by \"k\"
        target *= k
        #
        # s: temporary \"sum\" for the latest sub-array of size k
        s = 0
        for i in range(k):
            s += A[i]
        # res: Final result counter
        res     = 1 if s>=target else 0
        #
        for i in range( len(A) - k ):
            s   += - A[i] + A[i+k]
            res += 1 if s>=target else 0
        return res

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        start = 0
        s = 0
        count=0
        for end in range(len(arr)):
            s = s + arr[end]
            if end-start+1 == k:
                if s/k >= threshold:
                    count+=1
                s-=arr[start]
                start+=1
        return count


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        l, r = 0, k - 1
        res = 0
        s = sum(arr[:k])
        t = threshold * k
        while r < len(arr):
            if s >= t:
                res += 1
            if r + 1 < len(arr):
                s = s - arr[l] + arr[r + 1]
            l += 1
            r += 1
        return res

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        c = 0
        s = sum(arr[:k])
        if s/k >=threshold :
                c=1
        i = 1
        while i<= len(arr) - k:
            s = s - arr[i-1] + arr[i+k-1]
            if s/k >=threshold :
                c+=1
            i+=1
        return c

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        total = 0
        
        subarray = 0
        for i in range(k):
            subarray += arr[i] 
        average = subarray / k
        
        if average >= threshold:
            total += 1
        
        for i in range(len(arr) - k):
            subarray = subarray - arr[i] + arr[i + k]
            average = subarray / k
            if average >= threshold:
                total += 1
        
        
        return total

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        # lst_set = set()
        # arr_sort = sorted(arr, reverse = True)

        rolling_sum = sum(arr[:k])
        count = 0 if rolling_sum < threshold * k else 1
        for i in range(len(arr) - k):
            rolling_sum  = rolling_sum - arr[i] + arr[i + k]
            if rolling_sum >= threshold * k:
                count += 1
        return count



class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        c = 0
        i = 0
        s = sum(arr[:k])
        while i<= len(arr) - k:
            if i>0:
                s = s - arr[i-1] + arr[i+k-1]
            if s/k >=threshold :
                c+=1
            i+=1
        return c

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        res, curr = 0, 0
        for i, v in enumerate(arr):
            curr += v
            if i >= k:
                curr -= arr[i-k]
            if i >= k-1 and curr / k >= threshold:
                res += 1
        return res

class Solution:
    def numOfSubarrays(self, arr, k, threshold) -> int:
        s = 0
        sub = arr[0:k]
        subSum = sum(sub)
        avg = subSum/k
        if avg >= threshold:
            s += 1
        i = k
        j = 0
        while i < len(arr):
            subSum += arr[i]
            subSum -= arr[j]
            j += 1
            i += 1
            avg = subSum / k
            if avg >= threshold:
                s += 1
        return s


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        ans = 0
        running_sum = sum(arr[0:k])
        if running_sum/k >= threshold: ans+=1
        for x in range(len(arr)-k):
            running_sum+=arr[k+x]-arr[x]
            if running_sum/k >= threshold: ans+=1
        return ans


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        answer = 0

        avg = average(arr[0:k])
        prev_el = arr[0]

        if avg >= threshold: answer += 1

        for i in range(k, len(arr)):
            new_avg = (avg * k - prev_el + arr[i]) / k
            if new_avg >= threshold: answer += 1
            avg = new_avg
            prev_el = arr[i-k+1]

        return answer

def average(l):
    return sum(l) / len(l)