Given an array of size n, Find the subarray with least average of size k.
 
Example 1:
Input: nums = [30, 20, 10], k = 1
Output: 3
Explanation: Subarrays of length 1 are
{30}, {20}, {10}. {10} has the least 
average.
Example 2:
Input: nums = [30, 20, 10], k = 2
Output: 2
Explanation: Subarrays of length 2 are
{30, 20}, {20, 10}. {20, 10} has the least 
average.
 
Your Task:
You don't need to read or print anything. Yous task is to complete the function least_average() which takes the array and k as input parameter and returns the index of the first element of the subarray(1-based indexing) of size k that has least average.
 
Expected Time Complexity: O(n)
Expected Space Compelxity: O(1)
 
Constraints:
1 <= k <= n <= 100000
1 <= elements of array <= 1000000

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

	def least_average(self, nums, k):

		# Code here

Solutions:
class Solution:

	def least_average(self, nums, k):
		minAvg = 0
		avg = 0
		index = 1
		n = len(nums)
		for i in range(k):
			avg += nums[i]
		avg /= k
		minAvg = avg
		for i in range(1, n - k + 1):
			avg = avg * k - nums[i - 1] + nums[i + k - 1]
			avg /= k
			if minAvg > avg:
				minAvg = avg
				index = i + 1
		return index


class Solution:

	def least_average(self, nums, k):
		n = len(nums)
		if n < k:
			return -1
		curr_sum = sum(nums[:k])
		min_sum = curr_sum
		counter = 0
		for i in range(k, n):
			curr_sum += nums[i] - nums[i - k]
			if curr_sum < min_sum:
				min_sum = curr_sum
				counter = i - k + 1
		return counter + 1


class Solution:

	def least_average(self, nums, k):
		c = 1
		n = len(nums)
		s = sum(nums[:k])
		d = s
		for i in range(k, n):
			s += nums[i]
			s -= nums[i - k]
			if s < d:
				d = s
				c = i - k + 2
		return c


class Solution:

	def least_average(self, nums, k):
		sm = sum(nums[0:k])
		b = 0
		min = sm
		for i in range(len(nums) - k):
			sm = sm - nums[i]
			sm = sm + nums[i + k]
			if sm < min:
				min = sm
				b = i + 1
		return b + 1


class Solution:

	def least_average(self, nums, k):
		n = len(nums)
		current_sum = 0
		for i in range(k):
			current_sum += nums[i]
		min_index = 0
		min_sum = current_sum
		for i in range(k, n):
			current_sum = current_sum - nums[i - k] + nums[i]
			if current_sum < min_sum:
				min_index = i - k + 1
				min_sum = current_sum
		return min_index + 1


class Solution:

	def least_average(self, nums, k):
		n = len(nums)
		s = 0
		for i in range(k):
			s += nums[i]
		res = 1
		t = s
		for i in range(k, n):
			t = t - nums[i - k] + nums[i]
			if t < s:
				res = i - k + 2
				s = t
		return res


class Solution:

	def least_average(self, arr, k):
		if n < k:
			return 0
		res_index = 0
		curr_sum = sum(arr[0:k])
		min_sum = curr_sum
		for i in range(k, n):
			curr_sum += arr[i] - arr[i - k]
			if curr_sum < min_sum:
				min_sum = curr_sum
				res_index = i - k + 1
		return res_index + 1


class Solution:

	def least_average(self, nums, k):
		x = []
		first = sum(nums[:k])
		x.append(first / k)
		a = 0
		for i in range(k, len(nums)):
			first += nums[i]
			first -= nums[a]
			a += 1
			x.append(first / k)
		return x.index(min(x)) + 1


class Solution:

	def least_average(self, nums, k):
		if k == 1:
			return nums.index(min(nums)) + 1
		minavg = sum(nums[:k])
		currmin = minavg
		pos = 1
		for i in range(1, len(nums) - k + 1):
			minavg = minavg - nums[i - 1] + nums[i + k - 1]
			if minavg < currmin:
				currmin = minavg
				pos = i + 1
		return pos


import math

class Solution:

	def least_average(self, nums, k):
		n = len(nums)
		mn = math.inf
		ps = [0] * (n + 1)
		for j in range(n):
			ps[j + 1] = ps[j] + nums[j]
		idx = 0
		for i in range(n + 1 - k):
			mi = (ps[i + k] - ps[i]) / k
			if mi < mn:
				mn = mi
				idx = i + 1
		return idx


class Solution:

	def least_average(self, l, k):
		(s, n) = (0, len(l))
		for i in range(k):
			s += l[i]
		(m, a) = (s / k, 0)
		(i, j) = (0, k)
		while j < n:
			s += l[j]
			s -= l[i]
			if s / k < m:
				(m, a) = (s / k, i + 1)
			i += 1
			j += 1
		return a + 1


class Solution:

	def least_average(self, nums, k):
		ans_index = 0
		curr_sum = 0
		for i in range(k):
			curr_sum += nums[i]
		min_sum = curr_sum
		for i in range(k, n):
			curr_sum = curr_sum - nums[i - k] + nums[i]
			if curr_sum < min_sum:
				min_sum = curr_sum
				ans_index = i - k + 1
		return ans_index + 1


class Solution:

	def least_average(self, nums, k):
		n = len(nums)
		Sub_array = sum(nums[:k])
		Min_sum = Sub_array
		idx = 1
		for i in range(1, n - k + 1):
			Sub_array = Sub_array - nums[i - 1] + nums[i + k - 1]
			if Min_sum > Sub_array:
				Min_sum = Sub_array
				idx = i + 1
		return idx


class Solution:

	def least_average(self, nums, k):
		summ = sum(nums[0:k])
		avg = summ / k
		ans = 0
		for i in range(k, len(nums)):
			summ = summ + nums[i] - nums[i - k]
			if avg > summ / k:
				avg = summ / k
				ans = i - k + 1
		return ans + 1


class Solution:

	def least_average(self, nums, k):
		left = 0
		n = len(nums)
		avg = 0
		for i in range(k):
			avg += nums[i]
		avg /= k
		least = avg
		minleft = 0
		for right in range(k, n):
			avg += (nums[right] - nums[left]) / k
			left += 1
			if avg < least:
				least = avg
				minleft = left
		return minleft + 1


class Solution:

	def least_average(self, nums, k):
		curr_sum = sum(nums[:k])
		avg = curr_sum / k
		ans = 1
		for i in range(1, len(nums) - k + 1):
			curr_sum = curr_sum + nums[i + k - 1] - nums[i - 1]
			if curr_sum / k < avg:
				avg = min(avg, curr_sum / k)
				ans = i + 1
		return ans


class Solution:

	def least_average(self, nums, k):
		ans = 1
		if k == len(nums):
			return ans
		currsum = sum(nums[:k])
		minval = currsum
		for i in range(0, len(nums) - k):
			currsum = currsum - nums[i] + nums[i + k]
			if minval > currsum:
				minval = currsum
				ans = i + 2
		return ans


class Solution:

	def least_average(self, nums, k):
		pos = 0
		Sum = sum(nums[0:k])
		Minsum = Sum
		i = 0
		for j in range(k, len(nums)):
			Sum = Sum + nums[j] - nums[i]
			i += 1
			if Sum < Minsum:
				Minsum = Sum
				pos = i
		return pos + 1


class Solution:

	def least_average(self, nums, k):
		n = len(nums)
		summ = sum(nums)
		res = 1
		tam = summ
		for i in range(k, n):
			tam = tam - nums[i - k] + nums[i]
			if tam < summ:
				res = i - k + 2
				summ = tam
		return res


import sys

class Solution:

	def least_average(self, nums, k):
		sum_int = 0
		max_int = sys.maxsize
		end_idx = 0
		start_idx = 0
		least_average_start_idx = 0
		nums_length = len(nums)
		while end_idx < nums_length:
			if end_idx - start_idx + 1 < k:
				sum_int += nums[end_idx]
			else:
				sum_int += nums[end_idx]
				if sum_int / k < max_int:
					least_average_start_idx = start_idx
					max_int = sum_int / k
				sum_int -= nums[start_idx]
				start_idx += 1
			end_idx += 1
		return least_average_start_idx + 1


class Solution:

	def least_average(self, nums, k):
		sumi = 0
		maxi = 99999999999
		j = 0
		i = 0
		ans = 0
		while j < len(nums):
			if j - i + 1 < k:
				sumi += nums[j]
			else:
				sumi += nums[j]
				if sumi / k < maxi:
					ans = i
					maxi = sumi / k
				sumi -= nums[i]
				i += 1
			j += 1
		return ans + 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, k) = input().split()
		n = int(n)
		k = int(k)
		nums = list(map(int, input().split()))
		ob = Solution()
		ans = ob.least_average(nums, k)
		print(ans)


class Solution:

	def least_average(self, nums, k):
		i = 0
		min_so_far = float('inf')
		temp = 0
		arr = nums
		count = 0
		ans = 0
		for x in range(len(nums)):
			temp += arr[x]
			if x >= k - 1:
				count += 1
				if temp < min_so_far:
					ans = count
					min_so_far = temp
				temp -= arr[i]
				i += 1
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, k) = input().split()
		n = int(n)
		k = int(k)
		nums = list(map(int, input().split()))
		ob = Solution()
		ans = ob.least_average(nums, k)
		print(ans)


class Solution:

	def least_average(self, nums, k):
		n = len(nums)
		if n < k:
			return 0
		curr_sum = 0
		for i in range(k):
			curr_sum += nums[i]
		min_sum = curr_sum
		min_index = 0
		for i in range(k, n):
			curr_sum += nums[i] - nums[i - k]
			if min_sum > curr_sum:
				min_sum = curr_sum
				min_index = i - k + 1
		return min_index + 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, k) = input().split()
		n = int(n)
		k = int(k)
		nums = list(map(int, input().split()))
		ob = Solution()
		ans = ob.least_average(nums, k)
		print(ans)


import sys

class Solution:

	def least_average(self, nums, k):
		(l, r) = (0, k)
		s = sum(nums[:k])
		minAvg = s / k
		res = [0, k - 1]
		for i in range(k, len(nums)):
			s += nums[r]
			s -= nums[l]
			l += 1
			r += 1
			if s / k < minAvg:
				minAvg = s / k
				res = [l, r - 1]
		return res[0] + 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, k) = input().split()
		n = int(n)
		k = int(k)
		nums = list(map(int, input().split()))
		ob = Solution()
		ans = ob.least_average(nums, k)
		print(ans)


class Solution:

	def least_average(self, nums, k):
		if k == 1:
			m = min(nums)
			return nums.index(m) + 1
		s = sum(nums[:k])
		m = s
		ind = 1
		for i in range(1, len(nums) - k + 1):
			s = s - nums[i - 1] + nums[i + k - 1]
			if s < m:
				s = m
				ind = i + 1
		return ind


class Solution:

	def least_average(self, nums, k):
		A = nums[:k]
		c = 1
		ans = 1
		s = sum(A)
		minavg = s / k
		for i in range(k, len(nums)):
			s -= nums[i - k]
			s += nums[i]
			c += 1
			if s / k < minavg:
				minavg = s / k
				ans = c
		return ans


class Solution:

	def least_average(self, nums, k):
		n = len(nums)
		mini = 1
		mina = sum(nums[0:k]) / k
		s = sum(nums[0:k])
		for i in range(k, n):
			s -= nums[i - k]
			s += nums[i]
			a = s / k
			if a < mina:
				mini = i + 1 - k + 1
				mina = a
		return mini


class Solution:

	def least_average(self, nums, k):
		if len(nums) < k:
			return 0
		min = 10000
		cur_sum = 0
		for i in range(k):
			cur_sum = cur_sum + nums[i]
		min = cur_sum
		index = 0
		for i in range(k, len(nums)):
			cur_sum += nums[i] - nums[i - k]
			if cur_sum < min:
				min = cur_sum
				index = i - k + 1
		return index + 1


class Solution:

	def least_average(self, nums, k):
		i = 0
		j = 0
		sums = 0
		res = float('inf')
		index = -1
		while i < len(nums) and j < len(nums):
			sums += nums[j]
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if sums / k < res:
					res = sums / k
					index = i
				sums -= nums[i]
				i += 1
				j += 1
		return index + 1


class Solution:

	def least_average(self, nums, k):
		min_avg = 0
		for i in range(0, k):
			min_avg += nums[i]
		min_avg = min_avg
		min_index = 1
		curr_avg = min_avg
		for i in range(1, len(nums) - k + 1):
			curr_avg += nums[i + k - 1] - nums[i - 1]
			if curr_avg < min_avg:
				min_avg = curr_avg
				min_index = i + 1
		return min_index


class Solution:

	def least_average(self, nums, k):
		A = nums
		B = k
		left = 0
		right = B - 1
		average = 1000000000
		index = 0
		sumVal = sum(A[left:right + 1])
		while right < len(A):
			value = sumVal / B
			if value < average:
				average = value
				index = left
			sumVal -= A[left]
			left += 1
			right += 1
			if right < len(A):
				sumVal += A[right]
		return index + 1


class Solution:

	def least_average(self, nums, k):
		sum_till_now = 0
		for i in range(0, k):
			sum_till_now += nums[i]
		min_till_now = sum_till_now
		res = 0
		for i in range(k, len(nums)):
			sum_till_now = sum_till_now - nums[i - k] + nums[i]
			if sum_till_now < min_till_now:
				min_till_now = sum_till_now
				res = i - k + 1
		return res + 1


class Solution:

	def least_average(self, nums, k):
		sum_ = sum(nums[0:k])
		min_sum = sum_
		start = 0
		for i in range(k, len(nums)):
			sum_ = sum_ - nums[i - k] + nums[i]
			if sum_ < min_sum:
				min_sum = sum_
				start = i - k + 1
		return start + 1


class Solution:

	def least_average(self, arr, k):
		n = len(nums)
		if k > n:
			return None
		if k == 1:
			return nums.index(min(nums)) + 1
		min_sum = 0
		for i in range(k):
			min_sum += nums[i]
		result_index = 0
		current_sum = min_sum
		for i in range(k, n):
			current_sum += nums[i] - nums[i - k]
			if min_sum > current_sum:
				current_sum = min_sum
				result_index = i - k + 1
		return result_index + 1


class Solution:

	def least_average(self, nums, k):
		first_sum = 0
		for n in nums[:k]:
			first_sum += n
		sub_sum = [-1] * (len(nums) - k + 1)
		sub_sum[0] = first_sum
		min_sub_sum = first_sum
		min_idx = 1
		for i in range(1, len(nums) - k + 1):
			sub_sum[i] = sub_sum[i - 1] + nums[k + i - 1] - nums[i - 1]
			if sub_sum[i] < min_sub_sum:
				min_sub_sum = sub_sum[i]
				min_idx = i + 1
		return min_idx


class Solution:

	def least_average(self, nums, k):
		smallest = sum(nums[:k])
		last = smallest
		i = 0
		for n in range(1, len(nums) - k + 1):
			last += nums[n + k - 1]
			last -= nums[n - 1]
			if last < smallest:
				smallest = last
				i = n
		return i + 1


import math

class Solution:

	def least_average(self, nums, k):
		best_avg = math.inf
		best_idx = 0
		(curr_sum, new_sum) = (0, 0)
		for i in range(k):
			curr_sum += nums[i]
		best_sum = curr_sum
		for i in range(1, len(nums) - k + 1):
			new_sum = curr_sum + nums[i + k - 1] - nums[i - 1]
			if new_sum < best_sum:
				best_idx = i
				best_sum = new_sum
			curr_sum = new_sum
		return best_idx + 1


class Solution:

	def least_average(self, nums, k):
		res = 1
		summ = sum(nums[0:k])
		cur_sum = summ
		for i in range(k, len(nums)):
			cur_sum += nums[i] - nums[i - k]
			if cur_sum < summ:
				summ = cur_sum
				res = i - k + 2
		return res