Given an array A containing N integers.Find out how many elements should be added such that all elements between the maximum and minimum of the array is present in the array.
Example 1:
Input:
N=5
A=[205,173,102,324,957]
Output:
851
Explanation:
The maximum and minimum of given 
array is 957 and 102 respectively.We need 
to add 854 elements out of which
3 are already present.So answer is 851.
Example 2:
Input:
N=1
A=[545]
Output:
0
Explanation:
We don't need to add any element
to the array.
Your Task:
You don't need to read input or print anything. Your Task is to complete the function countElements() which takes an integer N and an array A of size N and returns the number of elements needed to be added to the array so, that all elements between the minimum and maximum of the array are present.
Expected Time Complexity:O(N)
Expected Auxillary Space:O(10^{5})
Constraints:
1<=N,A[i]<=10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def countElements(self,N,A):
        #code here

Solutions:
class Solution:

	def countElements(self, N, A):
		A.sort()
		ma = A[N - 1]
		mi = A[0]
		sum = 0
		for i in range(N - 1):
			if A[i + 1] == A[i] + 1:
				continue
			if A[i] == A[i + 1]:
				continue
			sum = sum + A[i + 1] - A[i] - 1
		return sum


class Solution:

	def countElements(self, N, A):
		m = max(A)
		mi = min(A)
		N = len(set(A))
		return m - mi - 1 - (N - 2)


class Solution:

	def countElements(self, N, A):
		n = len(set(A))
		mx = max(A)
		mn = min(A)
		ans = mx - mn - 1
		rec = n - 2
		if rec < 0:
			return 0
		else:
			return ans - rec


from collections import Counter

class Solution:

	def countElements(self, N, A):
		c = Counter(A)
		return max(c.keys()) - min(c.keys()) - len(c) + 1


class Solution:

	def countElements(self, N: int, A: list) -> int:
		(minimum, maximum) = (float('inf'), float('-inf'))
		for i in range(N):
			if A[i] < minimum:
				minimum = A[i]
			if A[i] > maximum:
				maximum = A[i]
		numbers = set(A)
		count = 0
		for number in range(minimum + 1, maximum):
			if number not in numbers:
				count += 1
		return count


class Solution:

	def countElements(self, N, A):
		maxi = max(A)
		mini = min(A)
		s = set()
		val = maxi - mini - 1
		for x in A:
			s.add(x)
		val = val - (len(s) - 2)
		return val


class Solution:

	def countElements(self, N, A):
		mi = min(A)
		ma = max(A)
		g = max(A) - min(A) - 1
		m = {}
		for i in A:
			if i > mi and i < ma:
				if i not in m:
					g -= 1
					m[i] = 1
		if g <= 0:
			return 0
		return g


class Solution:

	def countElements(self, N, A):
		n = len(set(A))
		minn = min(A)
		maxx = max(A)
		ans = maxx - minn - 1
		rec = n - 2
		if rec < 0:
			return 0
		else:
			return ans - rec


class Solution:

	def countElements(self, N, A):
		A = list(set(A))
		if N == 1:
			return 0
		a = min(A)
		b = max(A)
		A.remove(a)
		A.remove(b)
		Ans = b - a - 1
		for i in A:
			if i > a or i < b:
				Ans = Ans - 1
		return Ans


class Solution:

	def countElements(self, N, A):
		A = list(set(A))
		if N == 1:
			return 0
		k1 = max(A)
		k2 = min(A)
		return abs(k1 - k2 - 1 - (len(A) - 2))


class Solution:

	def countElements(self, N, A):
		mn = min(A)
		mx = max(A)
		st = set(A)
		if mx == mn:
			return 0
		return mx - mn - len(st) + 1


class Solution:

	def countElements(self, N, A):
		if N > 1:
			x = max(A)
			y = min(A)
			z = x - y - 1
			a = []
			for i in A:
				if i != x and i != y:
					a.append(i)
			b = len(set(a))
			return z - b
		else:
			return 0


class Solution:

	def countElements(self, N, A):
		hash = [0] * 100005
		minimum = 100005
		maximum = 0
		for i in A:
			hash[i] += 1
			maximum = max(maximum, i)
			minimum = min(minimum, i)
		ans = 0
		for i in range(minimum + 1, maximum):
			if hash[i] == 0:
				ans += 1
		return ans


class Solution:

	def countElements(self, N, A):
		X = list(set(A))
		return max(X) - min(X) - len(X) + 1


class Solution:

	def countElements(self, N, A):
		if N == 1:
			return 0
		a = max(A)
		b = min(A)
		m = {}
		for i in A:
			if i not in m:
				m[i] = 1
		if N == 2:
			return abs(A[0] - A[1] - 1)
		return a - b - (len(m) - 2) - 1


class Solution:

	def countElements(self, N, A):
		min_val = min(A)
		max_val = max(A)
		number_distinct = len(set(A))
		target_num_distinct = max_val - min_val + 1
		return target_num_distinct - number_distinct


class Solution:

	def countElements(self, N, A):
		d = max(A) - min(A)
		s = set(A)
		d2 = len(A) - len(s)
		return d - (N - 1) + d2


class Solution:

	def countElements(self, N, A):
		n = max(A) - min(A) - 1
		map = {}
		if n == -1:
			return 0
		for i in A:
			map[i] = 1
		for i in range(min(A) + 1, max(A)):
			if i in map:
				n = n - 1
		return n


class Solution:

	def countElements(self, N, A):
		count = 0
		if N == 1:
			return 0
		else:
			A.sort()
			difference = A[-1] - A[0]
			d = {}
			for e in A:
				if e not in d:
					d[e] = 1
			n = len(d)
			return difference - 1 - (n - 2)


class Solution:

	def countElements(self, N, arr):
		count = 0
		if N == 1:
			return 0
		else:
			arr.sort()
			for i in range(0, N - 1):
				if arr[i] != arr[i + 1] and arr[i] != arr[i + 1] - 1:
					count += arr[i + 1] - arr[i] - 1
			return count


class Solution:

	def countElements(self, N, A):
		if len(A) == 1:
			return 0
		min_ = min(A)
		max_ = max(A)
		d = {}
		for e in A:
			if e not in d:
				d[e] = 1
		n = len(d)
		return max_ - min_ - 1 - (len(d) - 2)