You are given an array arr[ ] of size N consisting of only positive integers. Your task is to find the count of special numbers in the array. A number is said to be a special number if it is divisible by at least 1 other element of the array.
Example 1:
Input:
N = 3
arr[] = {2, 3, 6}
Output:
1
Explanation:
The number 6 is the only special number in the
array as it is divisible by the array elements 2 
and 3. Hence, the answer is 1 in this case.
Example 2:
Input: 
N = 4
arr[] = {5, 5, 5, 5}
Output:
4
Explanation: 
All the array elements are special. Hence, 
the answer is 4 in this case.
Your Task:
You don't need to read input or print anything. Complete the function countSpecialNumbers() which takes the integer N and the array arr[ ] as the input parameters, and returns the count of special numbers in the array. 
Expected Time Complexity: O(N*root(M)) where M = max(arr[i])
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5 }
1 ≤ arr[i] ≤ 10^{6}^{ }

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

    def countSpecialNumbers(self, N, arr):

        # Code here

Solutions:
class Solution:

	def countSpecialNumbers(self, N, arr):
		ans = 0
		arr.sort()
		d = {}
		for i in arr:
			d[i] = d.get(i, 0) + 1
		for i in range(N):
			if d[arr[i]] > 1:
				ans += 1
			else:
				for j in range(i):
					if arr[i] % arr[j] == 0:
						ans += 1
						break
		return ans


from collections import Counter

class Solution:

	def countSpecialNumbers(self, N, arr):
		arr.sort()
		dic = Counter(arr)
		count = 0
		for i in range(N):
			if dic[arr[i]] > 1:
				count += 1
			else:
				j = 0
				while j < i:
					if arr[i] % arr[j] == 0:
						count += 1
						break
					j += 1
		return count


class Solution:

	def countSpecialNumbers(self, N, arr):
		c = 0
		arr = sorted(arr)
		dic = {}
		for i in arr:
			dic[i] = dic.get(i, 0) + 1
		for i in range(N):
			if dic[arr[i]] > 1:
				c += 1
			else:
				for j in range(i):
					if arr[i] % arr[j] == 0:
						c += 1
						break
		return c


from collections import Counter
from math import sqrt

class Solution:

	def countSpecialNumbers(self, N, arr):
		frequency = dict()
		maxVal = 0
		for i in arr:
			maxVal = max(i, maxVal)
			if i in frequency:
				frequency[i] += 1
			else:
				frequency[i] = 1
		specialNumbers = set()
		for i in frequency:
			for j in range(2 * i, maxVal + 1, i):
				if j in frequency:
					specialNumbers.add(j)
		ans = 0
		for ele in frequency.keys():
			if frequency[ele] > 1:
				ans += frequency[ele]
			elif ele in specialNumbers:
				ans += 1
		return ans


class Solution:

	def countSpecialNumbers(self, N, arr):
		arr.sort()
		di = {}
		for x in arr:
			di[x] = 0
		for x in arr:
			di[x] = di[x] + 1
		count = 0
		for i in range(len(arr)):
			if di[arr[i]] > 1:
				count = count + 1
			else:
				flag = 0
				for j in range(i):
					if arr[i] % arr[j] == 0:
						flag = 1
						break
				if flag == 1:
					count = count + 1
		return count


class Solution:

	def countSpecialNumbers(self, N, arr):
		max_element = max(arr)
		res = [0 for i in range(max_element + 1)]
		for i in arr:
			if res[i] <= 1:
				for j in range(i, max_element + 1, i):
					res[j] = res[j] + 1
		return sum((res[i] > 1 for i in arr))


class Solution:

	def countSpecialNumbers(self, N, arr):
		count = 0
		arr.sort()
		d = {x: 0 for x in arr}
		for i in arr:
			d[i] += 1
		for i in range(N):
			if d[arr[i]] > 1:
				count += 1
			else:
				for j in range(i):
					if arr[i] % arr[j] == 0:
						count += 1
						break
		return count


class Solution:

	def countSpecialNumbers(self, N, arr):
		m = max(arr)
		res = [0] * (m + 1)
		for a in arr:
			if res[a] <= 1:
				for b in range(a, m + 1, a):
					res[b] += 1
		return sum((res[a] > 1 for a in arr))


class Solution:

	def countSpecialNumbers(self, N, arr):
		ma = max(arr)
		mark = [-1] * (ma + 1)
		for a in arr:
			if mark[a] == -1:
				mark[a] = 1
				for i in range(a + a, ma + 1, a):
					mark[i] = 0
			elif mark[a] == 1:
				mark[a] = 0
		ans = 0
		for a in arr:
			if mark[a] == 0:
				ans += 1
		return ans


class Solution:

	def countSpecialNumbers(self, N, arr):
		m = max(arr)
		fact = [0 for i in range(m + 1)]
		for i in range(N):
			if fact[arr[i]] <= 1:
				for j in range(arr[i], m + 1, arr[i]):
					fact[j] += 1
		count = 0
		for i in range(N):
			if fact[arr[i]] > 1:
				count += 1
		return count


class Solution:

	def countSpecialNumbers(self, N, arr):
		frequency = dict()
		distinctElements = set()
		maxVal = 0
		for i in arr:
			distinctElements.add(i)
			maxVal = max(i, maxVal)
			if i in frequency:
				frequency[i] += 1
			else:
				frequency[i] = 1
		specialNumbers = set()
		for i in distinctElements:
			for j in range(2 * i, maxVal + 1, i):
				if j in distinctElements:
					specialNumbers.add(j)
		ans = 0
		for ele in frequency.keys():
			if frequency[ele] > 1:
				ans += frequency[ele]
			elif ele in specialNumbers:
				ans += 1
		return ans


class Solution:

	def countSpecialNumbers(self, N, arr):
		c = 0
		z = {}
		arr.sort()
		for i in arr:
			z[i] = z.get(i, 0) + 1
		for i in range(N):
			if z[arr[i]] > 1:
				c += 1
			else:
				for j in range(i):
					if arr[i] % arr[j] == 0:
						c += 1
						break
		return c


class Solution:

	def countSpecialNumbers(self, N, arr):
		c = 0
		m = max(arr)
		d = {}
		for i in range(N):
			if not arr[i] in d:
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
		arr.sort()
		for j in range(N):
			if d[arr[j]] > 1:
				c += 1
			else:
				for i in range(j):
					if arr[j] % arr[i] == 0:
						c += 1
						break
		return c


from collections import *

class Solution:

	def countSpecialNumbers(self, n, arr):
		ans = 0
		c = Counter(arr)
		for item in arr:
			flag = 0
			if c[item] > 1:
				ans += 1
				continue
			if item != 1 and c[1] >= 1:
				ans += 1
				continue
			for i in range(2, int(item ** 0.5) + 1):
				if item % i == 0 and (c[i] >= 1 or c[item // i] >= 1):
					flag = 1
					break
			if flag:
				ans += 1
		return ans


class Solution:

	def countSpecialNumbers(self, N, arr):
		n = len(arr)
		arr.sort()
		mx = max(arr)
		c = 0
		d = {}
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
		s = set(arr)
		ss = set()
		for i in d:
			if d[i] > 1:
				c += d[i]
				ss.add(i)
		sl = list(s)
		for i in sl:
			j = i + i
			while j < mx + 1:
				if j in s and j not in ss:
					c += 1
					ss.add(j)
				j += i
		return c


from collections import defaultdict
import math

class Solution:

	def countSpecialNumbers(self, N, arr):
		mp = defaultdict(set)
		count = 0
		for i in range(len(arr)):
			mp[arr[i]].add(i)
		if 1 in mp:
			count = N if len(mp[1]) > 1 else N - 1
			return count
		mx = max(arr)
		for i in range(N):
			if len(mp[arr[i]]) > 1:
				count += 1
				continue
			for j in range(2, int(math.sqrt(mx)) + 1):
				if arr[i] % j == 0 and (j in mp or arr[i] // j in mp):
					if arr[i] == j:
						continue
					count += 1
					break
		return count


class Solution:

	def countSpecialNumbers(self, N, arr):
		count_freq = dict()
		max_ele = max(arr)
		special = [False for i in range(0, max_ele + 1)]
		for x in arr:
			if x in count_freq:
				count_freq[x] += 1
				continue
			for i in range(2 * x, max_ele + 1, x):
				special[i] = True
			count_freq[x] = 1
		count = 0
		for p in arr:
			if special[p] or (p in count_freq and count_freq[p] > 1):
				count += 1
		return count


class Solution:

	def countSpecialNumbers(self, N, arr):
		from collections import Counter
		cnt = Counter(arr)
		arr.sort()
		ret = 0
		for i in range(N):
			if cnt[arr[i]] > 1:
				ret += 1
			else:
				for j in range(i):
					if arr[i] % arr[j] == 0:
						ret += 1
						break
		return ret


from collections import Counter
from math import sqrt as sq

class Solution:

	def countSpecialNumbers(self, N, arr):
		arr.sort()
		d = Counter(arr)
		c = 0
		for i in range(N):
			if d[arr[i]] > 1:
				c += 1
			else:
				j = 0
				while j < i:
					if arr[i] % arr[j] == 0:
						c += 1
						break
					j += 1
		return c


class Solution:

	def countSpecialNumbers(self, N, arr):
		d = {}
		count = 0
		for i in arr:
			d[i] = 1 + d.get(i, 0)
		arr.sort()
		j = 0
		while j < N:
			if d[arr[j]] > 1:
				count = count + 1
			else:
				for z in range(j):
					if arr[j] % arr[z] == 0:
						count = count + 1
						break
			j = j + 1
		return count


class Solution:

	def countSpecialNumbers(self, N, arr):
		freq = {}
		special = set()
		unique = set()
		maxi = 0
		for i in range(N):
			if arr[i] in freq:
				freq[arr[i]] += 1
			else:
				freq[arr[i]] = 1
			unique.add(arr[i])
			maxi = max(maxi, arr[i])
		for x in unique:
			for i in range(2 * x, maxi + 1, x):
				if i in unique:
					special.add(i)
		ans = 0
		for x in freq:
			if freq[x] > 1:
				ans += freq[x]
			elif x in special:
				ans += 1
		return ans


class Solution:

	def countSpecialNumbers(self, N, arr):
		m = max(arr)
		nums = [0] * (m + 1)
		for i in range(len(arr)):
			tar = arr[i]
			if nums[tar] < 2:
				for j in range(tar, m + 1, tar):
					nums[j] += 1
		ans = 0
		for i in range(len(arr)):
			if nums[arr[i]] > 1:
				ans += 1
		return ans


class Solution:

	def countSpecialNumbers(self, N, arr):
		count = 0
		len1 = len(arr)
		duplicate = {}
		count = {}
		for i in range(len1):
			if arr[i] not in duplicate:
				for j in range(len1):
					if i != j and arr[i] % arr[j] == 0:
						if arr[i] in count:
							count[arr[i]] += 1
						else:
							count[arr[i]] = 1
						break
				duplicate[arr[i]] = 1
			elif arr[i] in count:
				count[arr[i]] += 1
		return sum(count.values())


class Solution:

	def countSpecialNumbers(self, N, arr):
		max_num = max(arr)
		h_map = [0] * (max_num + 1)
		for i in range(N):
			if h_map[arr[i]] <= 1:
				for j in range(arr[i], max_num + 1, arr[i]):
					h_map[j] += 1
		ans = 0
		for i in range(N):
			if h_map[arr[i]] > 1:
				ans += 1
		return ans


class Solution:

	def countSpecialNumbers(self, N, arr):
		ans = 0
		special = set()
		frequency = dict()
		distinctnumbers = set(arr)
		maximum = max(arr)
		for i in distinctnumbers:
			for j in range(i * 2, maximum + 1, i):
				if j in distinctnumbers:
					special.add(j)
		for i in arr:
			if i in frequency:
				frequency[i] += 1
			else:
				frequency[i] = 1
		for i in frequency.keys():
			if frequency[i] > 1:
				ans += frequency[i]
			elif i in special:
				ans += 1
		return ans


from collections import Counter

class Solution:

	def countSpecialNumbers(self, N, arr):
		d = {}
		c = 0
		arr.sort()
		for i in arr:
			d[i] = d.get(i, 0) + 1
		for i in range(N):
			if d[arr[i]] > 1:
				c += 1
			else:
				for j in range(i):
					if arr[i] % arr[j] == 0:
						c += 1
						break
		return c


class Solution:

	def countSpecialNumbers(self, N, arr):
		mx = max(arr)
		ans = [0] * (mx + 1)
		for i in arr:
			if ans[i] <= 1:
				for j in range(i, mx + 1, i):
					ans[j] += 1
		count = 0
		for x in arr:
			if ans[x] > 1:
				count += 1
		return count


class Solution:

	def countSpecialNumbers(self, N, arr):
		freq = {}
		uniq = set()
		maximum = 0
		for i in range(N):
			freq[arr[i]] = freq.get(arr[i], 0) + 1
			uniq.add(arr[i])
			maximum = max(maximum, arr[i])
		special = set()
		for z in uniq:
			for i in range(2 * z, maximum + 1, z):
				if i in uniq:
					special.add(i)
		ans = 0
		for x in freq.items():
			if x[1] > 1:
				ans += x[1]
			elif x[0] in special:
				ans += 1
		return ans


class Solution:

	def countSpecialNumbers(self, N, arr):
		maxx = max(arr)
		a = [0] * (maxx + 1)
		for j in arr:
			if a[j] <= 1:
				for k in range(j, maxx + 1, j):
					a[k] += 1
		return sum((a[i] > 1 for i in arr))


class Solution:

	def countSpecialNumbers(self, N, arr):
		cnt = 0
		arr.sort()
		mp = {}
		for i in arr:
			if i not in mp:
				mp[i] = 1
			else:
				mp[i] += 1
		for i in range(N):
			if mp[arr[i]] > 1:
				cnt += 1
			else:
				for j in range(i):
					if arr[i] % arr[j] == 0:
						cnt += 1
						break
		return cnt


import math

class Solution:

	def countSpecialNumbers(self, n, a):
		d = {}
		for i in range(n):
			if a[i] not in d.keys():
				d[a[i]] = 1
			else:
				d[a[i]] += 1
		ans = 0
		for i in range(n):
			if a[i] == 1:
				if d[1] > 1:
					return n
				else:
					return n - 1
			for j in range(2, math.ceil(pow(a[i], 0.5) + 1)):
				if d[a[i]] > 1:
					ans += 1
					break
				elif j == a[i] and (j in d.keys() and d[a[i]] > 1):
					ans += 1
					break
				elif j != a[i] and a[i] % j == 0 and (j in d.keys() or a[i] // j in d.keys()):
					ans += 1
					break
		return ans


class Solution:

	def countSpecialNumbers(self, N, arr):
		cnt = 0
		d = {}
		maxi = max(arr)
		for i in range(N):
			curr = arr[i]
			if d.get(curr, 0) < 2:
				for j in range(curr, maxi + 1, curr):
					d[j] = 1 + d.get(j, 0)
		for i in range(N):
			curr = arr[i]
			if d[curr] > 1:
				cnt += 1
		return cnt


from collections import Counter

class Solution:

	def countSpecialNumbers(self, n, a):
		a.sort()
		c = 0
		d = Counter(a)
		for i in range(0, len(a)):
			if d[a[i]] > 1:
				c = c + 1
				continue
			else:
				for j in range(0, i):
					if a[i] % a[j] == 0:
						c = c + 1
						break
		return c


class Solution:

	def countSpecialNumbers(self, N, arr):
		m = max(arr)
		l = [0] * (m + 1)
		c = 0
		for i in range(N):
			if l[arr[i]] <= 1:
				j = arr[i]
				while j <= m:
					l[j] += 1
					j = j + arr[i]
		for i in range(N):
			if l[arr[i]] > 1:
				c += 1
		return c


class Solution:

	def countSpecialNumbers(self, N, arr):
		max_element = max(arr)
		temp_arr = [0 for i in range(max_element + 1)]
		for i in arr:
			if temp_arr[i] <= 1:
				for j in range(i, max_element + 1, i):
					temp_arr[j] = temp_arr[j] + 1
		count = 0
		for i in arr:
			if temp_arr[i] > 1:
				count += 1
		return count


class Solution:

	def countSpecialNumbers(self, N, arr):
		count = 0
		special = {}
		arr.sort()
		for i in arr:
			special[i] = special.get(i, 0) + 1
		for i in range(N):
			if special[arr[i]] > 1:
				count += 1
			else:
				for j in range(i):
					if arr[i] % arr[j] == 0 and j != i:
						count += 1
						break
		return count


from collections import Counter
import math

class Solution:

	def countSpecialNumbers(self, N, arr):
		d = Counter(arr)
		s = sorted(list(set(arr)), reverse=True)
		l = len(s)
		c = 0
		i = 0
		if s[-1] == 1:
			if d[1] == 1:
				return N - 1
			else:
				return N
		while i < l:
			t = s[i]
			f = 0
			limit = math.floor(math.sqrt(t))
			for j in range(2, limit + 1):
				if t % j == 0:
					if j in d or t // j in d:
						f = 1
						break
			if f == 1:
				c += d[t]
			elif d[t] > 1:
				c += d[t]
			i += 1
		return c


from collections import Counter

class Solution:

	def countSpecialNumbers(self, N, arr):
		mp = Counter(arr)
		st = set(arr)
		ans = 0
		for num in arr:
			j = 1
			while j * j <= num:
				if num % j == 0:
					if j in st:
						if num == 1 and j == 1:
							if mp[num] > 1:
								ans += 1
								break
						else:
							ans += 1
							break
					if j * j != num and num // j in st:
						if j == 1:
							if mp[num] > 1:
								ans += 1
								break
						else:
							ans += 1
							break
				j += 1
		return ans


from collections import Counter

class Solution:

	def countSpecialNumbers(self, n, arr):
		arr.sort()
		maxm = max(arr)
		counts = Counter(arr)
		sieve = [False] * (maxm + 1)
		visited = set()
		for i in arr:
			if i in visited:
				continue
			visited.add(i)
			cur = 2 * i
			while cur <= maxm:
				sieve[cur] = True
				cur += i
		res = 0
		for i in arr:
			if counts[i] > 1 or sieve[i]:
				res += 1
		return res


class Solution:

	def countSpecialNumbers(self, N, arr):
		m = max(arr)
		freq = [0 for _ in range(m + 1)]
		for i in arr:
			if freq[i] <= 1:
				for j in range(i, m + 1, i):
					freq[j] += 1
		count = sum((1 for i in arr if freq[i] > 1))
		return count