Lucky numbers are subset of integers. Rather than going into much theory, let us see the process of arriving at lucky numbers,
Take the set of integers
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,……
First, delete every second number, we get following reduced set.
1, 3, 5, 7, 9, 11, 13, 15, 17, 19,…………
Now, delete every third number, we get
1, 3, 7, 9, 13, 15, 19,….….
Continue this process indefinitely……
Any number that does NOT get deleted due to above process is called “lucky”.
Example 1:
Input:
N = 5
Output: 0
Explanation: 5 is not a lucky number 
as it gets deleted in the second 
iteration.
Example 2:
Input:
N = 19
Output: 1
Explanation: 19 is a lucky number
Your Task:
You don't need to read input or print anything. You only need to complete the function isLucky() that takes N as parameter and returns either False if the N is not lucky else True.
Expected Time Complexity: O(sqrt(N)).
Expected Auxiliary Space: O(sqrt(N)).
Constraints:
1 <= N <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Complete search

Starter code: #User function Template for python3

class Solution:
    def isLucky(self, n): 
        #RETURN True OR False

Solutions:
class Solution:

	def isLucky(self, n):
		i = 2
		while n >= i:
			if n % i == 0:
				return False
			n -= n // i
			i += 1
		return True


class Solution:

	def isLucky(self, n):

		def isl(n, c):
			if c <= n:
				if n % c == 0:
					return False
				n = n - n // c
				c += 1
				return isl(n, c)
			else:
				return True
		c = 2
		return isl(n, c)


class Solution:

	def result(self, n, counter):
		if n < counter:
			return True
		if n % counter == 0:
			return False
		n = n - n // counter
		return self.result(n, counter + 1)

	def isLucky(self, n):
		return self.result(n, 2)


class Solution:

	def isLucky(self, n):
		res = self.func(n, 2)
		return res

	def func(self, n, i):
		if i > n:
			return 1
		elif n % i == 0:
			return 0
		else:
			return self.func(n - n // i, i + 1)


class Solution:

	def isLucky(self, n):
		x = 2
		while x <= n:
			if n % x != 0:
				n = n - int(n / x)
				x += 1
			else:
				return False
		return True


class Solution:

	def is_lucky_number(self, n, k):
		if k > n:
			return True
		if n % k == 0:
			return False
		new_n = n - n // k
		return self.is_lucky_number(new_n, k + 1)

	def isLucky(self, n):
		return self.is_lucky_number(n, 2)


class Solution:

	def check(self, n, p):
		if p <= n:
			if n % p == 0:
				p = 2
				return False
			n = n - n // p
			p += 1
			return self.check(n, p)
		else:
			return True

	def isLucky(self, n):
		return self.check(n, 2)


class Solution:

	def isLucky(self, n, mod=2):
		if mod > n:
			return True
		if n % mod == 0:
			return False
		temp = n // mod
		return self.isLucky(n - temp, mod + 1)


class Solution:

	def isLucky(self, n):
		for i in range(2, n + 1):
			if n % i == 0:
				return False
			n -= n // i
		return True


class Solution:

	def isLucky(self, n):
		arr = [i for i in range(1, n + 1)]
		x = 2
		while x <= n:
			if n % x != 0:
				n = n - int(n / x)
				x += 1
			else:
				return False
		return True


class Solution:

	def isLucky(self, n):
		if n % 2 == 0:
			return False
		return self.luckynos(n, 2)

	def luckynos(self, n, i):
		if n == 1:
			return True
		if n % i == 0:
			return False
		if i > n:
			return True
		t = int(n / i)
		f = self.luckynos(n - t, i + 1)
		return f


class Solution:

	def isLucky(self, n):

		def helper(n, c):
			if n % c == 0:
				return False
			if n < c:
				return True
			return helper(n - n // c, c + 1)
		return helper(n, 2)


class Solution:

	def isLucky(self, n):
		return self.isLuckyHelper(1, n)

	def isLuckyHelper(self, iter, pos):
		if pos <= iter:
			return True
		if pos % (iter + 1) == 0:
			return False
		return self.isLuckyHelper(iter + 1, pos - pos // (iter + 1))


class Solution:

	def isLucky(self, n):
		return self.deleteNumbers(n, 2)

	def deleteNumbers(self, n, k):
		if n % k == 0:
			return False
		if k > n:
			return True
		return self.deleteNumbers(n - n // k, k + 1)


class Solution:

	def isLucky(self, n):

		def luc(n, count):
			if count > n:
				return True
			if n % count != 0:
				n = n - n // count
				count = count + 1
				return True and luc(n, count)
			else:
				return False
		return luc(n, 2)


class Solution:

	def solve(self, n, counter):
		if n % counter == 0:
			return False
		elif counter > n:
			return True
		return self.solve(n - n // counter, counter + 1)

	def isLucky(self, n):
		return self.solve(n, 2)


class Solution:

	def isLucky(self, n):

		def help(n, k):
			if n == 1:
				return 1
			if n % k == 0:
				return 0
			if k > n:
				return 1
			new_n = n - n // k
			k = k + 1
			return help(new_n, k)
		return help(n, 2)


class Solution:

	def solve(self, n, i):
		if n < i:
			return 1
		if n % i == 0:
			return 0
		n = n - n // i
		i += 1
		return self.solve(n, i)

	def isLucky(self, n):
		return self.solve(n, 2)


class Solution:

	def isLucky(self, n):
		i = 2
		a = 0
		while i <= n:
			if n % i == 0:
				return False
				break
			else:
				a = n // i
				n = n - a
				i += 1
		if i - n == 1:
			return True


import math

class Solution:

	def isLucky(self, n, index=3):
		if index == 3:
			if n < 5:
				return n & 1
			if ~n & 1:
				return False
			n = n // 2
		if not (n + 1) % index:
			return False
		if index > n:
			return True
		n = n - n // index
		return self.isLucky(n, index + 1)


class Solution:

	def ans(self, n, count):
		if count > n:
			return True
		if n % count == 0:
			return False
		n = n - n // count
		return self.ans(n, count + 1)

	def isLucky(self, n):
		return self.ans(n, 2)


class Solution:

	def isLucky(self, n):
		self.c = 2

		def sol(n):
			if n < self.c:
				return True
			if n % self.c == 0:
				return False
			k = n - n // self.c
			self.c += 1
			return sol(k)
		return sol(n)


class Solution:

	def isLucky(self, n):

		def lucky(num, position):
			if position > num:
				return True
			if num % position == 0:
				return False
			num -= num // position
			return lucky(num, position + 1)
		return lucky(n, 2)


class Solution:

	def checkLucky(self, N, n):
		if N < n:
			return True
		if N % n == 0:
			return False
		N = N - N // n
		return self.checkLucky(N, n + 1)

	def isLucky(self, n):
		return self.checkLucky(n, 2)


class Solution:

	def isLucky(self, n):

		def ans(cut, ind):
			if cut > ind:
				return True
			elif ind % cut == 0:
				return False
			ind = ind - int(ind / cut)
			cut += 1
			return ans(cut, ind)
		return ans(2, n)


class Solution:

	def isLucky(self, n):
		res = self.delete(2, n)
		return res

	def delete(self, itr, n):
		if itr > n:
			return True
		if n % itr == 0:
			return False
		next_position_of_n_in_list = n - n // itr
		ans = self.delete(itr + 1, next_position_of_n_in_list)
		return ans


class Solution:

	def helper(self, n, c):
		if c <= n:
			if n % c == 0:
				return 0
			n = n - n // c
			return self.helper(n, c + 1)
		else:
			return 1

	def isLucky(self, n):
		return self.helper(n, 2)


class Solution:

	def isLucky(self, n):
		count = 2

		def fun(n, count):
			if n < count:
				return 1
			if n % count == 0:
				return 0
			divide = n // count
			n = n - divide
			return fun(n, count + 1)
		return fun(n, count)