Given a sorted array of size N. Count the number of distinct absolute values present in the array.
 
Example 1:
Input:
N = 6
Arr[] = {-3, -2, 0, 3, 4, 5}
Output: 5
Explanation: There are 5 distinct absolute 
values i.e. 0, 2, 3, 4 and 5.
Example 2:
Input:
N = 9
Arr[] = {-1, -1, -1, -1, 0, 1, 1, 1, 1}
Output: 2
Explanation: There are 2 distinct absolute values 
among the elements of this array, i.e. 0 and 1.
Your Task:
You don't need to read input or print anything. Your task is to complete the function distinctCount() which takes the array of integers arr[] and its size n as input parameters and returns an integer denoting the answer.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
-10^{8} <= Arr[i] <= 10^{8}
The array may contain duplicates

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: 



class Solution:

    def distinctCount(self, arr, n):

        # code here

Solutions:
class Solution:

	def distinctCount(self, arr, n):
		s = [abs(x) for x in arr]
		s = list(set(s))
		return len(s)


class Solution:

	def distinctCount(self, arr, n):
		c = set()
		for i in arr:
			if i not in c:
				c.add(abs(i))
		return len(c)


class Solution:

	def distinctCount(self, arr, n):
		l = []
		for i in arr:
			l.append(abs(i))
		return len(set(l))


class Solution:

	def distinctCount(self, arr, n):
		d = {}
		for i in arr:
			d[abs(i)] = d.setdefault(abs(i), 0) + 1
		return len(d)


class Solution:

	def distinctCount(self, arr, n):
		for i in range(n):
			arr[i] = abs(arr[i])
		a = set(arr)
		b = list(a)
		return len(b)


class Solution:

	def distinctCount(self, arr, n):
		i = 0
		while i < n:
			if arr[i] < 0:
				arr[i] = abs(arr[i])
			i += 1
		return len(set(arr))


class Solution:

	def distinctCount(self, arr, n):
		s = set()
		for i in arr:
			s.add(abs(i))
		return len(s)


class Solution:

	def distinctCount(self, arr, n):
		for i in range(n):
			arr[i] = abs(arr[i])
		return len(set(arr))


class Solution:

	def distinctCount(self, arr, n):
		num = [abs(i) for i in arr]
		num = list(set(num))
		return len(num)


class Solution:

	def distinctCount(self, arr, n):
		i = 0
		j = n - 1
		prev = -10000000007
		next = 10000000007
		c = 0
		while i <= j:
			if abs(arr[i]) == abs(arr[j]):
				if arr[i] != prev and arr[j] != next:
					c += 1
				prev = arr[i]
				next = arr[j]
				i += 1
				j -= 1
			elif abs(arr[i]) < abs(arr[j]):
				if arr[j] != next:
					c += 1
				next = arr[j]
				j -= 1
			else:
				if arr[i] != prev:
					c += 1
				prev = arr[i]
				i += 1
		return c


class Solution:

	def distinctCount(self, arr, n):
		res = [abs(ele) for ele in arr]
		a = set(res)
		return len(a)


from collections import Counter

class Solution:

	def distinctCount(self, arr, n):
		return len(Counter(map(abs, arr)))


class Solution:

	def distinctCount(self, arr, n):
		ans = set()
		for e in arr:
			ans.add(abs(e))
		return len(ans)


class Solution:

	def distinctCount(self, arr, n):
		for i in range(n):
			if arr[i] < 0:
				arr[i] = -1 * arr[i]
		return len(set(arr))


class Solution:

	def distinctCount(self, arr, n):
		hmap = {}
		for i in arr:
			y = abs(i)
			if y not in hmap:
				hmap[y] = 1
			else:
				hmap[y] += 1
		return len(hmap)


class Solution:

	def distinctCount(self, arr, n):
		d = {}
		for i in arr:
			b = abs(i)
			if b not in d:
				d[b] = 1
		return len(d)


class Solution:

	def distinctCount(self, arr, n):
		m = [abs(i) for i in arr]
		l = list(set(m))
		return len(l)


class Solution:

	def distinctCount(self, arr, n):
		for i in range(n):
			if arr[i] < 0:
				arr[i] = -1 * arr[i]
		arr.sort()
		i = 1
		count = 1
		while i < n:
			if arr[i - 1] == arr[i]:
				i += 1
			else:
				count += 1
				i += 1
		return count


class Solution:

	def distinctCount(self, arr, n):
		ab = []
		for i in arr:
			ab.append(abs(i))
		return len(list(set(ab)))


class Solution:

	def distinctCount(self, arr, n):
		res = {}
		for i in range(n):
			if abs(arr[i]) not in res:
				res[abs(arr[i])] = 1
		return len(res)


class Solution:

	def distinctCount(self, arr, n):
		s = {}
		for i in arr:
			s[abs(i)] = 1
		return len(s)


class Solution:

	def distinctCount(self, arr, n):
		s = set()
		for x in arr:
			if x < 0:
				s.add(x * -1)
			else:
				s.add(x)
		return len(s)


class Solution:

	def distinctCount(self, arr, n):
		li = map(lambda x: -x if x < 0 else x, arr)
		se = set(li)
		return len(se)
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.distinctCount(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def distinctCount(self, arr, n):
		for i in range(n):
			arr[i] = abs(arr[i])
		a = set(arr)
		return len(a)
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.distinctCount(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def distinctCount(self, arr, n):
		dist_count = n
		l = 0
		h = n - 1
		while l < h:
			while arr[l] == arr[l + 1] and l < h:
				dist_count = dist_count - 1
				l = l + 1
			while arr[h] == arr[h - 1] and h > l:
				dist_count = dist_count - 1
				h = h - 1
			if l == h:
				break
			if arr[l] + arr[h] == 0:
				dist_count = dist_count - 1
				(l, h) = (l + 1, h - 1)
				continue
			if arr[l] + arr[h] > 0:
				h = h - 1
			else:
				l = l + 1
		return dist_count
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.distinctCount(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def distinctCount(self, arr, n):
		l = {}
		for i in arr:
			if abs(i) not in l:
				l[abs(i)] = 1
		return sum(l.values())


import bisect

class Solution:

	def distinctCount(self, a, n):
		num = [abs(i) for i in a]
		num = list(set(num))
		return len(num)


class Solution:

	def distinctCount(self, arr, n):
		l = 0
		r = n - 1
		cnt = 0
		while l <= r:
			while l < r and r > 0 and (arr[r - 1] == arr[r]):
				r = r - 1
			while l < r and l < n - 1 and (arr[l] == arr[l + 1]):
				l = l + 1
			if abs(arr[l]) == abs(arr[r]):
				l = l + 1
				r = r - 1
			elif abs(arr[l]) > abs(arr[r]):
				l = l + 1
			else:
				r = r - 1
			cnt = cnt + 1
		return cnt


class Solution:

	def distinctCount(self, arr, n):
		low = 0
		high = n - 1
		ans = n
		s = 0
		while low < high:
			while low != high and arr[low] == arr[low + 1]:
				ans -= 1
				low += 1
			while low != high and arr[high - 1] == arr[high]:
				ans -= 1
				high -= 1
			if low == high:
				break
			s = arr[low] + arr[high]
			if s == 0:
				ans -= 1
				low += 1
				high -= 1
			elif s > 0:
				high -= 1
			else:
				low += 1
		return ans


class Solution:

	def distinctCount(self, arr, n):
		count = 0
		gg = {}
		for i in arr:
			if i < 0:
				i = -i
			if i not in gg:
				gg[i] = 1
				count += 1
		return count


class Solution:

	def distinctCount(self, arr, n):
		u = []
		for i in range(len(arr)):
			u.append(abs(arr[i]))
		x = list(set(u))
		return len(x)


from collections import defaultdict

class Solution:

	def distinctCount(self, arr, n):
		d = defaultdict(lambda : 0)
		c = n
		for i in range(n - 1, -1, -1):
			if arr[i] >= 0:
				d[arr[i]] += 1
			else:
				x = abs(arr[i])
				if d[x] > 0:
					continue
		return len(d)


class Solution:

	def distinctCount(self, arr, n):
		cnt = n
		(i, j) = (0, n - 1)
		while i < j:
			while i != j and arr[i] == arr[i + 1]:
				i += 1
				cnt -= 1
			while i != j and arr[j] == arr[j - 1]:
				j -= 1
				cnt -= 1
			if i == j:
				break
			if arr[i] + arr[j] < 0:
				i += 1
			elif arr[i] + arr[j] > 0:
				j -= 1
			else:
				cnt -= 1
				i += 1
				j -= 1
		return cnt


class Solution:

	def distinctCount(self, arr, n):
		return len(set(sorted(map(abs, arr))))


class Solution:

	def distinctCount(self, arr, n):
		dictt = {}
		for ele in arr:
			ele = abs(ele)
			dictt[ele] = dictt.get(ele, 0) + 1
		return len(dictt)


class Solution:

	def distinctCount(self, arr, n):
		d = set()
		for i in arr:
			if i < 0:
				d.add(-1 * i)
			else:
				d.add(i)
		return len(list(d))


class Solution:

	def distinctCount(self, arr, n):
		c = 0
		i = 0
		j = len(arr) - 1
		prev = float('-inf')
		nextt = float('inf')
		while i <= j:
			if abs(arr[i]) == abs(arr[j]):
				if arr[i] != prev and arr[j] != nextt:
					c += 1
				prev = arr[i]
				nextt = arr[j]
				i += 1
				j -= 1
			elif abs(arr[i]) < abs(arr[j]):
				if arr[j] != nextt:
					c += 1
				nextt = arr[j]
				j -= 1
			elif abs(arr[i]) > abs(arr[j]):
				if arr[i] != prev:
					c += 1
				prev = arr[i]
				i += 1
		return c


class Solution:

	def distinctCount(self, arr, n):
		import numpy as np
		arr = [np.abs(i) for i in arr]
		return len(list(set(arr)))


class Solution:

	def distinctCount(self, arr, n):
		arr = list(set([abs(a) for a in arr]))
		return len(arr)