Given N leaves numbered from 1 to N . A caterpillar at leaf 1, jumps from leaf to leaf in multiples of A_{j} (A_{j}, 2A_{j}, 3A_{j}).
j is specific to the caterpillar. Whenever a caterpillar reaches a leaf, it eats it a little bit.. You have to find out how many leaves, from 1 to N, are left uneaten after all K caterpillars have reached the end. Each caterpillar has its own jump factor denoted by A_{j}, and each caterpillar starts at leaf number 1. 
Example 1:
Input:
N=10 K=3
arr[] = {2, 3, 5} 
Output: 2
Explanation: The leaves eaten by the first 
caterpillar are (2, 4, 6, 8, 10). The leaves 
eaten by the second caterpilllar are (3, 6, 9).
The leaves eaten by the third caterpilllar 
are (5, 10). Ultimately, the uneaten leaves are 
1, 7 and their number is 2.
 
Your Task:
Since this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function uneatenLeaves() that takes array arr, integer N, and integer K as parameters and returns the number of uneaten leaves.
 
Expected Time Complexity: O(N^{2}).
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N ≤ 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Mathematics

Starter code: #User function Template for python3




def uneatenLeaves(arr,n,k):
    # Your code goes here   

Solutions:
def uneatenLeaves(arr, n, k):
	res = 0
	for i in range(1, n + 1):
		flag = 0
		for j in arr:
			if i % j == 0:
				flag = 1
				break
		if flag != 1:
			res += 1
	return res


def uneatenLeaves(arr, n, k):
	s = 0
	for i in range(1, n + 1):
		for j in range(k):
			if i % arr[j] == 0:
				s += 1
				break
	return n - s


def uneatenLeaves(arr, n, k):
	count = 0
	for i in range(1, n + 1):
		flag = True
		for item in arr:
			if i % item == 0:
				flag = False
				break
		count += flag
	return count


def uneatenLeaves(arr, n, k):
	leaves = [0] * (n + 1)
	for i in arr:
		if i <= n and (not leaves[i]):
			for j in range(i, n + 1, i):
				leaves[j] = 1
	res = 0
	for i in range(1, n + 1):
		if not leaves[i]:
			res += 1
	return res


def uneatenLeaves(arr, n, k):
	dic = {}
	if 1 in arr:
		return 0
	for i in arr:
		for j in range(1, n + 1):
			if j % i == 0:
				dic[j] = 1
	return n - len(dic.keys())


def uneatenLeaves(arr, n, k):
	d = {}
	if 1 in arr:
		return 0
	for i in arr:
		if i not in d and i <= n:
			t = i
			mul = 2
			d[t] = True
			while t * mul <= n:
				d[t * mul] = True
				mul += 1
	return n - len(d)


def uneatenLeaves(arr, n, k):
	b = n
	for i in range(1, n + 1):
		for j in range(len(arr)):
			if i % arr[j] == 0:
				b = b - 1
				break
	return b


def uneatenLeaves(arr, n, k):
	count = 0
	for i in range(1, n + 1):
		flag = 0
		for j in range(len(arr)):
			if i % arr[j] == 0:
				flag = 1
				break
		if flag == 0:
			count += 1
	return count


def uneatenLeaves(arr, n, k):
	eat_count = 0
	eaten = False
	for num_leaf in range(1, n + 1):
		for num_jump in arr:
			if num_leaf % num_jump == 0:
				eaten = True
				break
		if eaten is True:
			eat_count += 1
		eaten = False
	leftover = n - eat_count
	return leftover


def uneatenLeaves(arr, n, k):
	c = 0
	for i in range(1, n + 1):
		j = 0
		while j < k:
			if i % arr[j] == 0:
				c += 1
				break
			j += 1
	return n - c


def uneatenLeaves(arr, n, k):
	res = [0] * (n + 1)
	co = 0
	for i in range(k):
		f = arr[i]
		if f == 1:
			return 0
		c = f
		while c <= n:
			if res[c] != 1:
				res[c] = 1
				co += 1
			c += f
	return n + 1 - co - 1


def uneatenLeaves(arr, n, k):
	l = [0] * (n + 1)
	for i in arr:
		if i == 1:
			return 0
		for j in range(i, n + 1, i):
			l[j] = 1
	return l[1:].count(0)


def uneatenLeaves(arr, n, k):
	l = set()
	for i in range(1, n + 1):
		for x in arr:
			if i % x == 0:
				l.add(i)
				break
	return n - len(l)


def uneatenLeaves(a, n, k):
	s = set()
	a = set(a)
	count = 0
	for i in range(1, n + 1):
		for j in a:
			if j * i <= n:
				s.add(j * i)
	for i in range(1, n + 1):
		if i not in s:
			count += 1
	return count


def uneatenLeaves(arr, n, k):
	s = set()
	if 1 in arr:
		return 0
	for i in range(1, n + 1, 1):
		s.add(i)
	p = set()
	for i in arr:
		for j in range(1, n + 1, 1):
			if j % i == 0 and j in s:
				s.remove(j)
	return len(s)


def uneatenLeaves(arr, n, k):
	c = 0
	for i in range(1, n + 1):
		if all((i % j != 0 for j in arr)):
			c += 1
	return c


def uneatenLeaves(arr, n, k):
	un_eaten_leaves_count = 0
	for leaf_index in range(1, n + 1):
		for jump_factor in arr:
			if leaf_index % jump_factor == 0:
				break
		else:
			un_eaten_leaves_count += 1
	return un_eaten_leaves_count


def uneatenLeaves(arr, n, k):
	eatenLeaves = [True] * (n + 1)
	count = n
	for i in arr:
		if i > n or eatenLeaves[i] == False:
			continue
		for j in range(i, n + 1, i):
			if eatenLeaves[j] == True:
				count -= 1
			eatenLeaves[j] = False
	return count


def uneatenLeaves(arr, n, k):
	l = [0] * (n + 1)
	m = {}
	for i in arr:
		if i in m:
			continue
		m[i] = 1
		j = 1
		while j * i <= n:
			l[j * i] = 1
			j += 1
	c = 0
	for i in range(1, n + 1):
		if l[i] == 0:
			c += 1
	return c


def uneatenLeaves(arr, n, k):
	r = [0] * (n + 1)
	c1 = 0
	for i in range(k):
		f = arr[i]
		if f == 1:
			return 0
		c = f
		while c <= n:
			if r[c] != 1:
				r[c] = 1
				c1 += 1
			c += f
	return n + 1 - c1 - 1


def uneatenLeaves(arr, n, k):
	ls = [0] * (n + 1)
	e = 0
	for i in range(k):
		f = arr[i]
		if f == 1:
			return 0
		else:
			c = f
			while c <= n:
				if ls[c] != 1:
					ls[c] = 1
					e += 1
				c += f
	return n + 1 - e - 1


def uneatenLeaves(arr, n, k):
	res = [0] * (n + 1)
	c = 0
	for i in range(k):
		leaf = arr[i]
		if leaf == 1:
			return 0
		x = leaf
		while x <= n:
			if res[x] != 1:
				res[x] = 1
				c += 1
			x += leaf
	return n + 1 - c - 1


def uneatenLeaves(arr, n, k):
	mark = [0] * (n + 1)
	for i in range(k):
		num = arr[i]
		if num == 1:
			return 0
		while num <= n:
			mark[num] = 1
			num += arr[i]
	ans = 0
	for i in range(1, n + 1):
		if mark[i] == 0:
			ans += 1
	return ans
t = int(input())
for _ in range(0, t):
	l = list(map(int, input().split()))
	n = l[0]
	k = l[1]
	a = list(map(int, input().split()))
	ans = uneatenLeaves(a, n, k)
	print(ans)


def uneatenLeaves(arr, n, k):
	total = [0] * (n + 1)
	for i in arr:
		if i == 1:
			return 0
		for j in range(i, n + 1, i):
			total[j - 1] = 1
	return n - sum(total)
t = int(input())
for _ in range(0, t):
	l = list(map(int, input().split()))
	n = l[0]
	k = l[1]
	a = list(map(int, input().split()))
	ans = uneatenLeaves(a, n, k)
	print(ans)


def uneatenLeaves(arr, n, k):
	eaten = [0] * (n + 1)
	count = 0
	for i in range(k):
		f = arr[i]
		if f == 1:
			return 0
		c = f
		while c <= n:
			if eaten[c] != 1:
				eaten[c] = 1
				count += 1
			c += f
	return n - count
t = int(input())
for _ in range(0, t):
	l = list(map(int, input().split()))
	n = l[0]
	k = l[1]
	a = list(map(int, input().split()))
	ans = uneatenLeaves(a, n, k)
	print(ans)


def uneatenLeaves(arr, n, k):
	leavesEatten = [False] * (n + 1)
	count = 0
	for (catterPillarNo, multiple) in enumerate(arr):
		jump = multiple
		if jump == 1:
			return 0
		while jump <= n:
			if leavesEatten[jump] == False:
				count += 1
				leavesEatten[jump] = True
			jump += multiple
	return n - count


def uneatenLeaves(arr, n, k):
	leavesEatten = [False] * (n + 1)
	leavesEatten[0] = True
	count = 0
	for (catterPillarNo, jump) in enumerate(arr):
		if jump == 1:
			return 0
		for num in range(1, n + 1):
			if leavesEatten[num] == True:
				continue
			if num % jump == 0:
				leavesEatten[num] = True
				count += 1
	return n - count


def uneatenLeaves(arr1, n, k):
	count = n
	arr2 = [True] * (n + 1)
	for j in arr1:
		if j <= n and arr2[j]:
			for i in range(j, n + 1, j):
				if arr2[i]:
					arr2[i] = False
					count -= 1
	return count


from math import *

def uneatenLeaves(arr, n, k):
	l = 0
	for i in range(1, n + 1):
		for j in range(k):
			if i % arr[j] == 0:
				l += 1
				break
	return n - l


def uneatenLeaves(arr, n, k):
	uneatean_leaves_set = set(range(1, n + 1))
	jump_set = set(arr)
	if 1 in jump_set:
		return 0
	for jump in jump_set:
		uneatean_leaves_set = uneatean_leaves_set - set(range(jump, n + 1, jump))
		if len(uneatean_leaves_set) == 0:
			return 0
	return len(uneatean_leaves_set)


def uneatenLeaves(arr, n, k):
	c = [True] * (n + 1)
	for i in arr:
		if i > n:
			continue
		if c[i] == True:
			for j in range(i, n + 1, i):
				c[j] = False
	d = 0
	for i in range(1, len(c)):
		if c[i] == True:
			d = d + 1
	return d


def uneatenLeaves(l, n, k):
	l1 = [i for i in range(1, n + 1)]
	for i in l1:
		for j in l:
			if i % j == 0:
				n -= 1
				break
	return n


def uneatenLeaves(arr, n, k):
	res = [0] * (n + 1)
	for i in arr:
		t = i
		if i < n + 1 and res[i] == 0:
			while t < n + 1:
				res[t] = 1
				t += i
	ans = 0
	for i in range(1, n + 1):
		if res[i] == 0:
			ans += 1
	return ans


def uneatenLeaves(arr, n, k):
	eaten = []
	for x in range(1, n + 1):
		for y in arr:
			if x % y == 0:
				eaten.append(x)
				break
	return n - len(eaten)


def uneatenLeaves(arr, n, k):
	arr1 = [0] * n
	arr = set(arr)
	for i in arr:
		for j in range(i, n + 1, i):
			arr1[j - 1] = 1
	return n - sum(arr1)


def uneatenLeaves(arr, n, k):
	if min(arr) != 1:
		remove_leaves = list()
		for Aj in arr:
			N = int(n // Aj)
			for i in range(1, N + 1):
				remove_leaves.append(i * Aj)
		remainder_leaves = [leaf for leaf in range(1, n + 1) if leaf not in remove_leaves]
		return len(remainder_leaves)
	else:
		return 0


def uneatenLeaves(arr, n, k):
	ans = 0
	for i in range(1, n + 1):
		found = False
		for x in arr:
			if i % x == 0:
				found = True
				break
		if found != True:
			ans += 1
	return ans


def uneatenLeaves(arr, n, k):
	ans = [0] * 1000005
	f = 0
	for i in range(1, n + 1):
		for j in range(k):
			if i % arr[j] == 0:
				f = f + 1
				break
	return n - f


def uneatenLeaves(arr, n, k):
	x = 0
	for i in range(1, n + 1):
		f = 0
		for j in range(0, k):
			if i % arr[j] == 0:
				f = 1
				break
		if f == 0:
			x = x + 1
	return x


def uneatenLeaves(A, n, K):
	count = 0
	for i in range(1, n + 1):
		for x in A:
			if i % x == 0:
				count += 1
				break
	count = n - count
	return count