N frogs are positioned at one end of the pond. All frogs want to reach the other end of the pond as soon as possible. The pond has some leaves arranged in a straight line. Each frog has the strength to jump exactly K leaves. For example, a  frog having strength 2 will visit the leaves 2, 4, 6, ...  etc. while crossing the pond. 
Given the strength of each frog and the number of leaves, your task is to find the number of leaves that not be visited by any of the frogs when all frogs have reached the other end of the pond. 
Example 1:
Input:
N = 3
leaves = 4
frogs[] = {3, 2, 4} 
Output: 1
Explanation:
Leaf 1 will not be visited by any frog.
Example 2:
Input: 
N = 3
leaves = 6
frogs[] = {1, 3, 5} 
Output: 0
Explanation: 
First frog will visit all the leaves so no 
leaf is left unvisited.
Your Task:
Complete the function unvisitedLeaves() which takes the integers N, leaves and the array frogs as the input parameters, and returns the number of unvisited leaves.
Expected Time Complexity: O(N*log(leaves))
Expected Auxiliary Space: O(leaves)
Constraints:
1 ≤ N, leaves, frogs[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

    def unvisitedLeaves(self, N, leaves, frogs):

        # code here

Solutions:
class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		leaveStatus = [0 for j in range(leaves + 1)]
		for i in range(N):
			if frogs[i] <= leaves and leaveStatus[frogs[i]] == 0:
				for j in range(frogs[i], leaves + 1, frogs[i]):
					leaveStatus[j] = 1
		leafCount = leaves
		for i in leaveStatus:
			if i:
				leafCount -= 1
		return leafCount


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		frogs.sort()
		v = [0] * (leaves + 1)
		for i in range(N):
			if frogs[i] > leaves:
				continue
			if not v[frogs[i]]:
				for j in range(frogs[i], leaves + 1, frogs[i]):
					v[j] = 1
		ans = 0
		for i in v:
			ans += not i
		return ans - 1


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		arr = [0] * (leaves + 1)
		ans = 0
		for i in range(N):
			if frogs[i] <= leaves and arr[frogs[i]] == 0:
				for j in range(frogs[i], leaves + 1, frogs[i]):
					arr[j] = 1
		for i in arr[1:]:
			if i == 0:
				ans += 1
		return ans


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		visited = [0] * (leaves + 1)
		for i in range(N):
			st = frogs[i]
			if st <= leaves and (not visited[st]):
				for j in range(st, leaves + 1, st):
					visited[j] = 1
		c = 0
		for i in range(1, len(visited)):
			if visited[i] == 0:
				c += 1
		return c


from collections import defaultdict

class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		ans = 0
		m = defaultdict(int)
		for i in range(1, leaves + 1):
			m[i] = 0
		for i in frogs:
			if i < leaves + 1 and m[i] == 0:
				for j in range(i, leaves + 1, i):
					m[j] = 1
		for (k, v) in m.items():
			if v == 0:
				ans += 1
		return ans


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		hashh = [False for _ in range(leaves + 1)]
		for frog in frogs:
			if frog <= leaves and (not hashh[frog]):
				for i in range(0, leaves + 1, frog):
					hashh[i] = True
		return hashh.count(False)


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		left = [0] * leaves
		for i in range(N):
			num = frogs[i]
			n = num
			if num < leaves and left[num - 1] > 0:
				continue
			if num <= leaves:
				while n <= leaves:
					left[n - 1] += 1
					n += num
		count = 0
		for i in range(len(left)):
			if left[i] == 0:
				count += 1
		return count


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		d = {}
		for i in range(len(frogs)):
			j = 1
			if frogs[i] == 1:
				return 0
			if frogs[i] <= leaves and frogs[i] not in d:
				while frogs[i] * j <= leaves:
					if frogs[i] * j not in d:
						d[frogs[i] * j] = 1
					j += 1
		return leaves - len(d)


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		ls = [True] * (leaves + 1)
		count = leaves
		for j in frogs:
			if j == 1:
				return 0
			if ls[j % leaves] == True:
				for i in range(j, leaves + 1, j):
					if i % j == 0 and ls[i] == True:
						ls[i] = False
						count -= 1
		return count


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		arr = [1] * leaves
		old_frogs = []
		old_frogs = frogs[:]
		j = 0
		while j < len(frogs):
			if frogs[j] <= leaves and arr[frogs[j] - 1] == 1:
				if frogs[j] <= leaves:
					arr[frogs[j] - 1] = 0
					x = frogs[j]
					x += old_frogs[j]
					while x <= leaves and arr[x - 1] == 0:
						x += old_frogs[j]
					if x <= leaves:
						frogs[j] = x
						j -= 1
			j += 1
		return sum(arr)


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		leaves_list = [0 for _ in range(leaves)]
		seen = set()
		for i in frogs:
			if i in seen:
				continue
			else:
				seen.add(i)
				for j in range(i - 1, len(leaves_list), i):
					leaves_list[j] = 1
		unvisited_leaves = 0
		for i in leaves_list:
			if i == 0:
				unvisited_leaves += 1
		return unvisited_leaves


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		unvis = 0
		vis = [False] * (leaves + 1)
		for i in range(N):
			curr = frogs[i]
			if curr <= leaves and vis[curr] == False:
				for j in range(curr, leaves + 1, curr):
					vis[j] = True
		for i in range(1, leaves + 1):
			if vis[i] == False:
				unvis += 1
		return unvis


from collections import Counter

class Solution:

	def unvisitedLeaves(self, N, leaves, arr):
		if 1 in frogs:
			return 0
		visited = [0] * (leaves + 1)
		for i in range(N):
			cur = arr[i]
			if cur <= leaves and visited[cur] == 0:
				for j in range(cur, leaves + 1, cur):
					visited[j] = 1
		d = Counter(visited)
		return d[0] - 1


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		lst = [True] * (leaves + 1)
		for i in range(N):
			if frogs[i] < leaves + 1 and lst[frogs[i]]:
				for j in range(0, leaves + 1, frogs[i]):
					lst[j] = False
		cnt = 0
		for i in lst:
			if i:
				cnt += 1
		return cnt


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		frogs.sort()
		ans = [0] * leaves
		for i in range(0, len(frogs)):
			a = frogs[i]
			if a - 1 > leaves:
				break
			if ans[a - 1] != 0:
				continue
			while a <= leaves:
				ans[a - 1] = 1
				a += frogs[i]
		final_ans = 0
		for i in range(0, len(ans)):
			if ans[i] == 0:
				final_ans += 1
		return final_ans


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		visited = [0 for i in range(leaves + 1)]
		visited[0] = 1
		for i in range(N):
			if frogs[i] <= leaves and visited[frogs[i]] == 0:
				for j in range(frogs[i], leaves + 1, frogs[i]):
					visited[j] = 1
		count = 0
		for i in range(len(visited)):
			if visited[i] == 0:
				count += 1
		return count


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		frogs.sort()
		st = set(range(1, leaves + 1))
		for i in frogs:
			if i in st:
				st -= set(range(i, leaves + 1, i))
		return len(st)


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		visited = set()
		for i in sorted(frogs):
			if i not in visited:
				for j in range(i, leaves + 1, i):
					visited.add(j)
		count = 0
		for i in range(1, leaves + 1):
			if i not in visited:
				count += 1
		return count


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		a = [1 for x in range(leaves + 1)]
		count = 0
		for i in range(N):
			if i == 0 or frogs[i] % frogs[i - 1] != 0:
				for j in range(0, leaves + 1, frogs[i]):
					if a[j - 1] != 0:
						a[j - 1] = 0
						count = count + 1
		return leaves - count + 1


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		unvisit = 0
		visited = [False for i in range(leaves + 1)]
		for i in range(0, len(frogs)):
			curr = frogs[i]
			if curr <= leaves and visited[curr] == False:
				for j in range(curr, leaves + 1, curr):
					visited[j] = True
		for i in range(1, leaves + 1):
			if visited[i] == False:
				unvisit += 1
		return unvisit


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		res = set()
		for strength in frogs:
			if strength not in res:
				for j in range(strength, leaves + 1, strength):
					res.add(j)
		return leaves - len(res)


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		ls = [1] * (leaves + 1)
		res = leaves
		for i in frogs:
			if i == 1:
				return 0
			if ls[i % leaves] == 1:
				for k in range(i, leaves + 1, i):
					if ls[k] == 1 and k % i == 0:
						ls[k] = 0
						res -= 1
		return res


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		visited = [0] * (leaves + 1)
		for i in frogs:
			temp = i
			if i <= leaves and visited[i] == 0:
				while i <= leaves:
					visited[i] = True
					i += temp
		c = 0
		for i in range(1, leaves + 1):
			if not visited[i]:
				c += 1
		return c


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		ds = set()
		for i in range(N):
			if frogs[i] not in ds:
				for j in range(frogs[i], leaves + 1, frogs[i]):
					ds.add(j)
		c = 0
		for i in range(1, leaves + 1):
			if i not in ds:
				c += 1
		return c


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		my = [False for _ in range(leaves + 1)]
		for i in frogs:
			if i <= leaves and (not my[i]):
				for j in range(0, leaves + 1, i):
					my[j] = True
		return my.count(False)


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		visited = [False] * (leaves + 1)
		for i in range(N):
			num = frogs[i]
			if num <= leaves and (not visited[num]):
				for j in range(num, leaves + 1, num):
					visited[j] = True
		visited[0] = True
		unvisited = visited.count(False)
		return unvisited


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		unvis = 0
		vis = [0] * (leaves + 1)
		for i in range(N):
			curpos = frogs[i]
			if curpos <= leaves and (not vis[curpos]):
				for j in range(curpos, leaves + 1, curpos):
					vis[j] = True
		for i in range(1, leaves + 1):
			if not vis[i]:
				unvis += 1
		return unvis


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		frogs = sorted(frogs)
		leaves = [1 for i in range(leaves + 1)]
		for f in frogs:
			if f <= len(leaves) and leaves[f] == 1:
				for i in range(0, len(leaves), f):
					leaves[i] = 0
		return sum(leaves)


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		if 1 in frogs:
			return 0
		visited = [False] * (leaves + 1)
		for i in frogs:
			if i <= leaves and visited[i] == False:
				for idx in range(i, leaves + 1, i):
					visited[idx] = True
		cnt = 0
		for child in visited[1:]:
			if child == False:
				cnt += 1
		return cnt


class Solution:

	def unvisitedLeaves(self, N, leaves, frog):
		frogs.sort()
		co = 0
		uv = [0] * (leaves + 1)
		for i in range(N):
			if frog[i] > leaves:
				continue
			if not uv[frog[i]]:
				for j in range(frog[i], leaves + 1, frog[i]):
					uv[j] = 1
		for k in uv:
			if k == 0:
				co += 1
		return co - 1


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		visited = [False] * (leaves + 1)
		unvisted_count = leaves
		for frog in frogs:
			if frog == 1:
				return 0
			if frog <= leaves and (not visited[frog]):
				for multiple in range(0, leaves + 1, frog):
					if not visited[multiple]:
						visited[multiple] = True
						unvisted_count -= 1
		return unvisted_count + 1


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		a = [0] * (leaves + 1)
		for i in range(N):
			k = frogs[i]
			if k <= leaves and a[k] == 0:
				for j in range(k, len(a), k):
					a[j] = 1
		ans = 0
		for i in range(1, len(a)):
			if a[i] == 0:
				ans += 1
		return ans


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		vis = 0
		isVis = [False for i in range(leaves + 1)]
		for i in range(N):
			cur = frogs[i]
			if cur <= leaves and (not isVis[cur]):
				for k in range(cur, leaves + 1, cur):
					isVis[k] = True
		for i in range(1, leaves + 1):
			if isVis[i] == False:
				vis += 1
		return vis


class Solution:

	def unvisitedLeaves(self, N, l, a):
		p = [0] * (l + 1)
		for i in a:
			if i <= l and p[i] == 0:
				for j in range(i, l + 1, i):
					p[j] = 1
		count = 0
		for i in range(1, l + 1):
			if p[i] == 0:
				count += 1
		return count


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		if 1 in frogs:
			return 0
		res = [0] * (leaves + 1)
		for i in frogs:
			if i <= leaves and res[i] == 0:
				for j in range(1, int(leaves / i) + 1):
					res[i * j] += 1
		return res.count(0) - 1


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		ar = [0 for _ in range(leaves + 1)]
		for num in frogs:
			if num > leaves or not ar[num] == 0:
				continue
			for i in range(num, leaves + 1, num):
				ar[i] = 1
		return ar.count(0) - 1


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		vis = [0] * (leaves + 1)
		for i in frogs:
			if i <= leaves and vis[i] == 0:
				for j in range(i, leaves + 1, i):
					vis[j] = 1
		c = 0
		for i in range(1, leaves + 1):
			if vis[i] == 0:
				c += 1
		return c


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		l = set()
		for i in range(1, leaves + 1):
			l.add(i)
		j = 0
		while j < N:
			curr = frogs[j]
			if curr in l:
				while curr <= leaves:
					if curr in l:
						l.remove(curr)
					curr += frogs[j]
				j += 1
			else:
				j += 1
		if len(l) == 0:
			return 0
		return len(l)


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		visit = [0] * (leaves + 1)
		for i in range(N):
			pos = frogs[i]
			if pos <= leaves and visit[pos] == 0:
				temp = pos
				while temp <= leaves:
					if visit[temp] == 0:
						visit[temp] = 1
					temp = temp + pos
		return visit.count(0) - 1


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		flags = [False] * leaves
		for i in set(frogs):
			for j in range(i - 1, leaves, i):
				flags[j] = True
		return flags.count(False)


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		leaveStatus = [0 for j in range(leaves + 1)]
		for i in range(N):
			if frogs[i] <= leaves and leaveStatus[frogs[i]] == 0:
				for j in range(frogs[i], leaves + 1, frogs[i]):
					leaveStatus[j] = 1
		leafCount = leaves
		for i in leaveStatus:
			if i:
				leafCount -= 1
		return leafCount
		a = []
		b = leaves
		for i in range(leaves):
			if (i + 1) % frogs[0] == 0:
				a.append(1)
				b = b - 1
			else:
				a.append(0)
		for i in range(1, N):
			if frogs[i] <= leaves and a[frogs[i] - 1] == 0:
				for j in range(frogs[i], leaves + 1, frogs[i]):
					if a[j - 1] != 1:
						a[j - 1] = 1
						b = b - 1
			if b == 0:
				break
		return b


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		frogs = list(set(frogs))
		frogs.sort()
		if frogs[0] == 1:
			return 0
		muliples = [leaves // j for j in frogs]
		options = []
		for i in range(len(frogs)):
			for j in range(1, muliples[i] + 1):
				options.append(frogs[i] * j)
		count = len(list(set(options)))
		return leaves - count


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		if 1 in frogs:
			return 0
		ll = [x for x in range(1, leaves + 1)]
		frogs = sorted(frogs)
		p = 0
		while p < len(frogs):
			if frogs[p] > leaves:
				p += 1
				continue
			elif ll[frogs[p] - 1] != -1:
				ll[frogs[p] - 1] = -1
				for i in range(frogs[p], leaves + 1, frogs[p]):
					ll[i - 1] = -1
			p += 1
		ll = [z for z in ll if z != -1]
		return len(ll)


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		f = [0 for i in range(leaves + 1)]
		for x in frogs:
			if x == 1:
				return 0
			if x > leaves:
				continue
			if f[x]:
				continue
			for i in range(x, leaves + 1, x):
				f[i] = 1
		return leaves - sum(f)


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		seive = [True] * (leaves + 1)
		for i in range(N):
			curr = frogs[i]
			if frogs[i] == 1:
				return 0
			elif curr <= leaves and seive[curr]:
				for j in range(curr, leaves + 1, curr):
					if seive[j]:
						seive[j] = False
		cnt = 0
		for i in range(1, leaves + 1):
			if seive[i]:
				cnt += 1
		return cnt


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		d = {i + 1: True for i in range(leaves)}
		for i in frogs:
			if i <= leaves and (not d[i]):
				continue
			for j in range(i, leaves + 1, i):
				d[j] = False
		c = 0
		for i in d:
			if d[i]:
				c += 1
		return c


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		ju = set(frogs)
		ans = set()
		for j in ju:
			for i in range(j, leaves + 1, j):
				ans.add(i)
		return leaves - len(ans)


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		ans = 0
		v = [False] * (leaves + 1)
		for i in range(N):
			curr = frogs[i]
			if curr <= leaves and v[curr] == False:
				for j in range(curr, leaves + 1, curr):
					v[j] = True
		for i in range(1, leaves + 1):
			if v[i] == False:
				ans += 1
		return ans


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		visited = [False] * (leaves + 1)
		for frog in frogs:
			if frog <= leaves and visited[frog] == True:
				continue
			for i in range(frog, leaves + 1, frog):
				visited[i] = True
		cnt = 0
		for i in range(1, leaves + 1):
			if visited[i] == False:
				cnt += 1
		return cnt


class Solution:

	def unvisitedLeaves(self, N, leaves, frogs):
		hsh = [False for _ in range(leaves + 1)]
		for f in frogs:
			if f <= leaves and (not hsh[f]):
				for i in range(0, leaves + 1, f):
					hsh[i] = True
		return hsh.count(False)