Geek is a software engineer. He is assigned with the task of calculating average waiting time of all the processes by following shortest job first policy.
The shortest job first (SJF) or shortest job next, is a scheduling policy that selects the waiting process with the smallest execution time to execute next.
Given an array of integers bt of size n. Array bt denotes the burst time of each process. Calculate the average waiting time of all the processes and return the nearest integer which is smaller or equal to the output.
Note: Consider all process are available at time 0.
Example 1:
Input:
n = 5
bt = [4,3,7,1,2]
Output: 4
Explanation: After sorting burst times by shortest job policy, calculated average waiting time is 4.
Example 2:
Input:
n = 4
arr = [1,2,3,4]
Output: 2
Explanation: After sorting burst times by shortest job policy, calculated average waiting time is 2.
Your Task:
You don't need to read input or print anything. Your task is to complete the function solve() which takes bt[] as input parameter and returns the average waiting time of all the processes.
Expected Time Complexity: O(n^{2})
Expected Auxiliary Space: O(n)
Constraints:
1 <= n <= 100
1 <= arr[i] <= 100

Difficulty: MEDIUM
Expected Time Complexity: O(nlog(n))
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def solve(self, bt):

        # Code here

Solutions:
class Solution:

	def solve(self, bt):
		bt.sort()
		w = [0] * len(bt)
		for i in range(1, len(bt)):
			w[i] = bt[i - 1] + w[i - 1]
		return sum(w) // len(bt)


class Solution:

	def solve(self, bt):
		bt.sort()
		time = 0
		total = 0
		for b in bt:
			time += total
			total += b
		return time // len(bt)


class Solution:

	def solve(self, bt):
		(s, d) = (0, 0)
		bt.sort()
		for i in bt:
			s += i
			d += s - i
		return d // len(bt)


class Solution:

	def solve(self, bt):
		bt.sort()
		wait = 0
		total_time = 0
		for ele in bt:
			total_time += wait
			wait += ele
		return total_time // len(bt)


class Solution:

	def solve(self, bt):
		n = len(bt)
		curr = 0
		sum = 0
		bt.sort()
		for i in range(n):
			curr += bt[i]
			bt[i] = curr - bt[i]
			sum += bt[i]
		return sum // n


class Solution:

	def solve(self, bt):
		bt.sort()
		size = len(bt)
		curr = 0
		out = 0
		for i in range(size - 1):
			curr += bt[i]
			out += curr
		return out // size


class Solution:

	def solve(self, bt):
		bt.sort()
		(sum, diff) = (0, 0)
		for i in range(len(bt)):
			sum += bt[i]
			diff += sum - bt[i]
		return diff // len(bt)


from math import floor

class Solution:

	def solve(self, bt):
		n = len(bt)
		bt.sort()
		curr_time = 0
		summ = 0
		for i in range(n):
			curr_time += bt[i]
			bt[i] = curr_time - bt[i]
			summ += bt[i]
		return floor(summ / n)


class Solution:

	def solve(self, bt):
		n = len(bt)
		total = 0
		wt = [0] * (n + 1)
		p = [i + 1 for i in range(n)]
		for i in range(n):
			pos = i
			for j in range(i + 1, n):
				if bt[j] < bt[pos]:
					pos = j
			(bt[i], bt[pos]) = (bt[pos], bt[i])
			(p[i], p[pos]) = (p[pos], p[i])
		for i in range(1, n):
			for j in range(i):
				wt[i] += bt[j]
			total += wt[i]
		avg_wt = total // n
		return avg_wt


class Solution:

	def solve(self, bt):
		n = len(bt)
		if len(bt) == 1:
			return 0
		bt.sort()
		wt = []
		s = bt[0]
		for i in range(1, len(bt)):
			wt.append(s)
			s += bt[i]
		s = 0
		for i in range(len(wt)):
			s += wt[i]
		return s // n


class Solution:

	def solve(self, bt):
		bt.sort()
		sum = []
		x = 0
		for i in bt:
			x += i
			sum.append(x)
		ans = 0
		for i in sum:
			ans += i
		ans -= x
		ans = ans / len(bt)
		return int(ans)


class Solution:

	def solve(self, bt):
		bt.sort()
		n = len(bt)
		totalWait = 0
		wait = 0
		for i in range(n - 1):
			wait += bt[i]
			totalWait += wait
		avg = totalWait // n
		return avg


class Solution:

	def solve(self, bt):
		bt.sort()
		n = len(bt)
		prefix = [0] * n
		prefix[0] = bt[0]
		for i in range(1, n):
			prefix[i] = prefix[i - 1] + bt[i]
		s = 0
		for i in range(n - 1):
			s += prefix[i]
		return s // n


class Solution:

	def solve(self, bt):
		bt.sort()
		wt = 0
		tt = 0
		for x in bt:
			if tt == 0:
				tt += x
			else:
				wt += tt
				tt += x
		return wt // len(bt)


class Solution:

	def solve(self, bt):
		bt.sort()
		res = [0]
		wt = bt[0]
		for i in range(1, n):
			res.append(wt)
			wt += bt[i]
		avg = sum(res) // len(res)
		return avg


class Solution:

	def solve(self, bt):
		bt.sort()
		ct = []
		count = 0
		sum = 0
		for i in range(len(bt)):
			ct.append(bt[i] + count)
			sum += ct[i] - bt[i]
			count += bt[i]
		return sum // len(bt)


class Solution:

	def solve(self, bt):
		bt.sort()
		total = 0
		grand = 0
		for i in range(len(bt)):
			grand += total
			total = total + bt[i]
		return grand // len(bt)


class Solution:

	def solve(self, bt):
		bt.sort()
		t = 0
		s = 0
		for i in range(len(bt) - 1):
			t += bt[i]
			s += t
		return s // len(bt)


class Solution:

	def solve(self, bt):
		waiting_time = 0
		time = 0
		bt.sort()
		for i in range(len(bt)):
			waiting_time += time
			time += bt[i]
		return waiting_time // len(bt)


class Solution:

	def solve(self, bt):
		bt.sort()
		avg = 0
		time = 0
		total_wait = 0
		for i in bt:
			total_wait += time
			time += i
		return total_wait // len(bt)


class Solution:

	def solve(self, bt):
		bt.sort()
		ans = 0
		time = 0
		for i in bt:
			ans += time
			time += i
		return ans // len(bt)


class Solution:

	def solve(self, bt):
		bt.sort()
		n = len(bt)
		temp = bt[0]
		wt = 0
		for i in range(1, n):
			wt += temp
			temp += bt[i]
		return wt // n