Given a positive number X. Find the largest Jumping Number which is smaller than or equal to X. 
Jumping Number: A number is called Jumping Number if all adjacent digits in it differ by only 1. All single-digit numbers are considered as Jumping Numbers. For example 7, 8987 and 4343456 are Jumping numbers but 796, 677 and 89098 are not.
 
Example 1:
Input:
X = 10
Output:
10
Explanation:
10 is the largest Jumping Number
possible for X = 10.
Example 2:
Input:
X = 50
Output:
45
Explanation:
45 is the largest Jumping Number
possible for X = 50.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function jumpingNums() which takes an Integer X as input and returns the largest Jumping Number less than or equal to X.
 
Expected Time Complexity:  O(k), where k is no of jumping numbers
Expected Auxiliary Space: O(k), where k is no of jumping numbers 
 
Constraints:
1 <= X <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def jumpingNums(self, X):

        # code here 

Solutions:
from collections import deque

class Solution:

	def generate_all_jumping_nums(self, X, i):
		J = deque()
		J.append(i)
		while J:
			num = J.popleft()
			if num <= X:
				self.ans = max(self.ans, num)
				last_dig = num % 10
				if last_dig != 9:
					J.append(num * 10 + last_dig + 1)
				if last_dig != 0:
					J.append(num * 10 + last_dig - 1)

	def jumpingNums(self, X):
		self.ans = 0
		for i in range(1, 10):
			if i <= X:
				self.generate_all_jumping_nums(X, i)
		return self.ans


class Solution:

	def jumpingNums(self, X):
		lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]
		ans = 0
		while lst:
			num = lst.pop()
			if num > X:
				continue
			ans = max(num, ans)
			l = num % 10
			if l != 0:
				lst.append(num * 10 + (l - 1))
			if l != 9:
				lst.append(num * 10 + (l + 1))
		return ans


from collections import deque

class Solution:

	def jumpingNums(self, X):
		qu = deque()
		for i in range(10):
			qu.append(i)
		ans = 0
		while qu:
			num = qu.popleft()
			if num > X:
				continue
			ans = max(ans, num)
			lastdigit = num % 10
			if lastdigit != 0:
				first = num * 10 + (lastdigit - 1)
				qu.append(first)
			if lastdigit != 9:
				second = num * 10 + (lastdigit + 1)
				qu.append(second)
		return ans


class Solution:

	def jumpingNums(self, X):
		q = list(range(1, 10))
		ans = float('-inf')
		while q:
			x = q.pop()
			if x > X:
				continue
			ans = max(ans, x)
			d = x % 10
			if d != 9:
				q.append(x * 10 + d + 1)
			if d != 0:
				q.append(x * 10 + d - 1)
		return ans


class Solution:

	def jumpingNums(self, X):

		def bfs(n):
			q = [n]
			maxi = 0
			while q:
				num = q.pop()
				if num <= X:
					maxi = max(maxi, num)
					lastDigit = num % 10
					if lastDigit == 9:
						q.append(num * 10 + lastDigit - 1)
					elif lastDigit == 0:
						q.append(num * 10 + lastDigit + 1)
					else:
						q.append(num * 10 + lastDigit - 1)
						q.append(num * 10 + lastDigit + 1)
			return maxi
		ans = 0
		for i in range(1, 10):
			ans = max(ans, bfs(i))
		return ans


from collections import deque as dq

class Solution:

	def isEdge(self, x):
		if x < 11:
			return (True, x)
		else:
			return (False, 0)

	def intToList(self, x):
		res = []
		while x > 0:
			res.append(x % 10)
			x //= int(10)
		res.reverse()
		return res

	def listToInt(self, inp) -> int:
		if inp == None or len(inp) == 0:
			return -1
		res = inp[0]
		for i in range(1, len(inp)):
			res *= 10
			res += inp[i]
		return res

	def maxInt(self, inp1: list, inp2: list) -> int:
		return max(self.listToInt(inp1), self.listToInt(inp2))

	def isLE(self, listInp: list, intInp: int) -> bool:
		return self.listToInt(listInp) <= intInp

	def consider(self, prefix: list, right: list, x):
		if prefix[-1] not in range(10):
			return None
		if not self.isLE(prefix + right, x):
			return None
		if len(right) == 0:
			return prefix
		newRight = right[1:]
		bPrefix = prefix + [prefix[-1] + 1]
		sPrefix = prefix + [prefix[-1] - 1]
		bRes = self.consider(bPrefix, newRight, x)
		sRes = self.consider(sPrefix, newRight, x)
		if bRes and self.isLE(bRes, x):
			return bRes
		elif sRes and self.isLE(sRes, x):
			return sRes
		else:
			return None

	def jumpingNums(self, x):
		(isE, res) = self.isEdge(x)
		if isE:
			return res
		digits = self.intToList(x)
		b = self.consider([digits[0]], digits[1:], x)
		if digits[0] - 1 == 0:
			digits = [9] * (len(digits) - 1)
			digits[0] = 10
		s = self.consider([digits[0] - 1], digits[1:], x)
		return self.maxInt(b, s)


from collections import deque

class Solution:

	def jumpingNums(self, X):
		if X <= 0:
			return
		if X <= 10:
			return X
		level = 0
		num = X
		while num > 0:
			level += 1
			num //= 10
		q = deque([i for i in range(1, 10)])
		res = 0
		while q:
			cur = q.popleft()
			if cur > X:
				continue
			res = max(cur, res)
			tail = cur % 10
			if tail != 0:
				new_num1 = cur * 10 + tail - 1
				if new_num1 <= X:
					q.append(new_num1)
			if tail != 9:
				new_num2 = cur * 10 + tail + 1
				if new_num2 <= X:
					q.append(new_num2)
		return res


class Solution:

	def jumpingNums(self, x):
		queue = []
		if x <= 9:
			return x
		for i in range(1, 10):
			queue.append(i)
		i = 0
		num1 = 0
		num2 = 0
		while num1 <= x or num2 <= x:
			digit = queue[i]
			rem = digit % 10
			num1 = digit * 10 + rem - 1
			num2 = digit * 10 + rem + 1
			if rem == 0:
				if num2 <= x:
					queue.append(num2)
			elif rem == 9:
				if num1 <= x:
					queue.append(num1)
			else:
				if num1 <= x:
					queue.append(num1)
				if num2 <= x:
					queue.append(num2)
			i = i + 1
		return queue[len(queue) - 1]


from collections import deque

class Solution:

	def jumpingNums(self, X):
		ans = 0
		for i in range(1, 10):
			q = []
			q.append(i)
			while q:
				num = q.pop(0)
				if num <= X:
					ans = max(ans, num)
					lastdigit = num % 10
					if lastdigit == 0:
						q.append(num * 10 + (lastdigit + 1))
					elif lastdigit == 9:
						q.append(num * 10 + (lastdigit - 1))
					else:
						q.append(num * 10 + (lastdigit - 1))
						q.append(num * 10 + (lastdigit + 1))
		return ans


class Solution:

	def jumpingNums(self, X):
		if X <= 9:
			return X
		diff = X
		ans = 0

		def solve(v):
			nonlocal ans, diff
			if v > X:
				return
			if v <= X and v > ans:
				ans = v
				diff = X - v
			rem = v % 10
			if rem > 0:
				solve(v * 10 + rem - 1)
			if rem < 9:
				solve(v * 10 + rem + 1)
			return
		for i in range(1, 10):
			solve(i)
		return ans


class Solution:

	def jumpingNums(self, X):
		q = [i for i in range(1, 10)]
		ans = [0]
		while q:
			num = q.pop(0)
			if num <= X:
				ans.append(num)
				lastd = num % 10
				if lastd == 9:
					q.append(num * 10 + lastd - 1)
				elif lastd == 0:
					q.append(num * 10 + lastd + 1)
				else:
					q.append(num * 10 + lastd - 1)
					q.append(num * 10 + lastd + 1)
		return max(ans)


import sys

class Solution:

	def jumpingNums(self, X):
		if X < 10:
			return X
		q = [1, 2, 3, 4, 5, 6, 7, 8, 9]
		maxi = -sys.maxsize - 1
		while q:
			cur = q.pop(0)
			maxi = max(maxi, cur)
			lastdig = cur % 10
			if lastdig != 0:
				jump = 10 * cur + lastdig - 1
				if jump <= X:
					q.append(jump)
			if lastdig != 9:
				jump = 10 * cur + lastdig + 1
				if jump <= X:
					q.append(jump)
		return maxi


class Solution:

	def jumpingNums(self, X):
		if X <= 10:
			return X
		else:
			length = len(str(X))
			power = length - 1
			digitX = [int(X / 10 ** (power - i)) % 10 for i in range(length)]
			digitJ = [0] * length
			digitJ[0] = digitX[0]
			increase = 0
			flag = True
			for i in range(length - 1):
				a = digitJ[i]
				b = digitX[i + 1]
				if flag == False:
					for (idx, j) in enumerate(range(i + 1, length)):
						a = digitJ[j - 1]
						if a <= 8:
							digitJ[j] = a + 1
						else:
							digitJ[j] = a - 1
					break
				if a + 1 <= b:
					digitJ[i + 1] = a + 1
					increase = i + 1
					if a + 1 < b:
						flag = False
					continue
				if a - 1 <= b and a - 1 >= 0:
					digitJ[i + 1] = a - 1
					if a - 1 < b:
						flag = False
					continue
				if a == 0:
					digitJ[i - 1] -= 1
					for (idx, j) in enumerate(range(i, length)):
						digitJ[j] = 9 if idx % 2 == 0 else 8
					break
				if increase > 0:
					digitJ[increase] -= 2
				else:
					digitJ[increase] -= 1
				for j in range(increase + 1, length):
					d = digitJ[j - 1]
					if d <= 8:
						digitJ[j] = d + 1
					else:
						digitJ[j] = d - 1
				break
			answer = 0
			for (i, digit) in enumerate(digitJ):
				answer += digit * 10 ** (power - i)
			return answer


class Solution:

	def fun(self, arr, numSoFar, prev, i, l):
		if i == l:
			return numSoFar
		mx1 = 0
		mx2 = 0
		if prev != 9:
			tmp = numSoFar * 10 + (prev + 1)
			if arr[i] >= tmp:
				mx1 = max(numSoFar, self.fun(arr, tmp, prev + 1, i + 1, l))
		if prev != 0:
			tmp = numSoFar * 10 + (prev - 1)
			if arr[i] >= tmp:
				mx2 = max(numSoFar, self.fun(arr, tmp, prev - 1, i + 1, l))
		return max(numSoFar, mx1, mx2)

	def jumpingNums(self, X):
		if X < 11:
			return X
		l = len(str(X))
		arr = [0] * l
		i = l - 1
		while X:
			arr[i] = X
			X //= 10
			i -= 1
		res = 0
		res = max(res, self.fun(arr, arr[0], arr[0], 1, l))
		if len(str(res)) == l:
			return res
		if arr[0] != 1:
			res = max(res, self.fun(arr, arr[0] - 1, arr[0] - 1, 1, l))
		else:
			res = 9
			for _ in range(l - 2):
				if res % 10 == 9:
					res = res * 10 + 8
				else:
					res = res * 10 + 9
		return res


class Solution:

	def jumpingNums(self, X):
		if X in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
			return X
		ans = [0]

		def jump(s, ans, num):
			if s > num:
				return
			ans[0] = max(ans[0], s)
			ldigit = s % 10
			if ldigit != 9:
				jump(s * 10 + ldigit + 1, ans, num)
			if ldigit != 0:
				jump(s * 10 + ldigit - 1, ans, num)
			return
		num = X
		for i in range(1, 10):
			jump(i, ans, num)
		return ans[0]


from collections import deque

class Solution:

	def jumpingNums(self, x):
		if x <= 10:
			return x
		ans = []
		d = deque()
		for i in range(1, 10):
			d.append(i)
		while len(d) != 0:
			temp = d.popleft()
			if temp <= x:
				ans = temp
			remainder = temp % 10
			l_temp = temp * 10 + remainder - 1
			r_temp = temp * 10 + remainder + 1
			if l_temp <= x and remainder != 0:
				d.append(l_temp)
			if r_temp <= x and remainder != 9:
				d.append(r_temp)
		return ans


from math import log10

class Solution:

	def jumpingNums(self, X):
		exp = int(log10(X))
		a1 = a2 = d1 = d2 = X // 10 ** exp
		a3 = d3 = a1 - 1
		if a3 == 0:
			d3 = 8
		flip = 0
		for _ in range(exp):
			d1 += 1 if d1 == 0 else -1
			a1 = a1 * 10 + d1
			d2 -= 1
			a2 = a2 * 10 + d2
			d3 += -1 if d3 == 9 else 1
			a3 = a3 * 10 + d3
			flip = flip * 10 + 2
		if a1 > X:
			return a3
		digit = X // 10 ** exp
		while flip:
			if digit < 9 and a2 + flip <= X:
				a2 += flip
				digit += 1
			else:
				digit -= 1
			flip //= 10
		return a2


class Solution:

	def jumpingNums(self, X):
		q = []
		ans = -1
		for i in range(1, 10):
			if i < X:
				ans = max(ans, i)
				q.append(i)
			if i == X:
				return X
		while q:
			y = q.pop(0)
			ld = y % 10
			if ld != 0:
				z = y * 10 + ld - 1
				if z == X:
					return X
				if z < X:
					q.append(z)
					ans = max(ans, z)
			if ld != 9:
				z = y * 10 + ld + 1
				if z == X:
					return X
				if z < X:
					q.append(z)
					ans = max(ans, z)
		return ans


from collections import deque

class Solution:

	def jumpingNums(self, X):
		qu = deque()
		for i in range(10):
			qu.append(i)
		res = 0
		while qu:
			num = qu.popleft()
			if num > X:
				continue
			res = max(res, num)
			ld = num % 10
			if ld != 0:
				f = num * 10 + (ld - 1)
				qu.append(f)
			if ld != 9:
				s = num * 10 + (ld + 1)
				qu.append(s)
		return res


class Solution:

	def jumpingNums(self, X):
		q = []
		for i in range(1, 10):
			q.append(i)
		ans = 0
		while len(q) > 0:
			num = q.pop()
			if num > X:
				continue
			ans = max(ans, num)
			last = num % 10
			if last != 0:
				first = num * 10 + (last - 1)
				q.append(first)
			if last != 9:
				second = num * 10 + (last + 1)
				q.append(second)
		return ans


from collections import deque

class Solution:

	def jumpingNums(self, X):
		if 0 < X <= 9:
			return X
		ans = 0
		for i in range(1, 10):
			q = deque()
			q.append(i)
			while len(q) > 0:
				a = q.popleft()
				if a <= X:
					ans = max(ans, a)
					lastd = a % 10
					r = a * 10 + lastd + 1
					l = a * 10 + lastd - 1
					if lastd == 0:
						q.append(r)
					elif lastd == 9:
						q.append(l)
					else:
						q.append(r)
						q.append(l)
		return ans


class Solution:

	def isJumpingNumber(self, A, alen, X):
		if X <= 10:
			return (1, 0)
		prev = -1
		cnt = 0
		i = 0
		while i < alen:
			if prev >= 0:
				if abs(prev - A[i]) != 1:
					return (0, cnt)
			prev = A[i]
			i += 1
			cnt += 1
		return (1, cnt)

	def StrToArray(self, __S, __A):
		zord = ord('0')
		for i in range(len(__S)):
			__A.append(ord(__S[i]) - zord)

	def gt(self, O, n):
		if n > 1:
			if O[n - 1] > O[n - 2]:
				O[n - 1] = O[n - 2] - 1
			else:
				sidx = 1
				if O[0] < O[1]:
					O[1] = O[0] - 1
					sidx = 2
				else:
					O[0] -= 1
				for i in range(sidx, n):
					O[i] = O[i - 1] + 1 if O[i - 1] < 9 else O[i - 1] - 1
		else:
			O[n - 1] -= 1

	def lt(self, O, n):
		n = n

	def eq(self, O, n):
		if O[n] == 0:
			O[n - 1] -= 1
			O[n] = O[n - 1] + 1 if O[n - 1] > 0 else 9

	def simpler(self, A, jn_cnt):
		X = 0
		O = []
		for i in range(jn_cnt):
			O.append(A[i])
		p = 0
		if O[-1] > A[jn_cnt]:
			self.gt(O, jn_cnt)
			p = O[-1] + 1 if O[-1] < 9 else O[-1] - 1
		elif O[-1] < A[jn_cnt]:
			self.lt(O, jn_cnt - 1)
			p = O[-1] + 1 if O[-1] < 9 else O[-1] - 1
		else:
			self.eq(O, jn_cnt - 1)
			if A[jn_cnt] > 0:
				p = A[jn_cnt] - 1
			else:
				p = O[-1] - 1
		for i in range(jn_cnt, len(A)):
			O.append(p)
			p = p + 1 if p < 9 else p - 1
		for i in range(len(A)):
			X *= 10
			X += O[i]
		return X

	def jumpingNums(self, X):
		sX = str(X)
		A = []
		self.StrToArray(sX, A)
		(is_jn, jn_cnt) = self.isJumpingNumber(A, len(A), X)
		if is_jn:
			return X
		__X = self.simpler(A, jn_cnt)
		return __X


from collections import deque

class Solution:

	def jumpingNums(self, X):
		q = deque()
		ans = 0
		for i in range(1, 10):
			q.append(i)
		while q:
			num = q.popleft()
			if num > X:
				continue
			ans = max(ans, num)
			last_digit = num % 10
			if last_digit != 0:
				first_num = num * 10 + (last_digit - 1)
				q.append(first_num)
			if last_digit != 9:
				second_num = num * 10 + (last_digit + 1)
				q.append(second_num)
		return ans


class Solution:

	def jumpingNums(self, X):
		ans = []
		for e in range(1, 10):
			queue = [e]
			while queue:
				front = queue.pop(0)
				if front <= X:
					ans.append(front)
					lastDigit = front % 10
					if lastDigit == 9:
						leftNo = front * 10 + 8
						queue.append(leftNo)
					elif lastDigit == 0:
						rightNo = front * 10 + 1
						queue.append(rightNo)
					else:
						leftNo = front * 10 + (lastDigit - 1)
						rightNo = front * 10 + (lastDigit + 1)
						queue.append(leftNo)
						queue.append(rightNo)
		return max(ans)


from collections import deque

class Solution:

	def ljn(self, a, n):
		q = deque()
		q.append(n)
		while q:
			n = q.popleft()
			if n <= a:
				self.b = max(self.b, n)
				ld = n % 10
				if ld != 9:
					q.append(n * 10 + (ld + 1))
				if ld != 0:
					q.append(n * 10 + (ld - 1))

	def jumpingNums(self, a):
		self.b = 0
		for i in range(1, 10):
			if i <= a:
				self.ljn(a, i)
		return self.b


class Solution:

	def jumpingNums(self, X):
		q = [i for i in range(10)]
		ans = float('-inf')
		pos = 0
		len1 = 1
		while pos < len1:
			num = q[pos]
			if num > X:
				break
			ans = max(ans, num)
			lastdigit = num % 10
			if lastdigit != 0:
				q.append(num * 10 + (lastdigit - 1))
				len1 += 1
			if lastdigit != 9:
				q.append(num * 10 + (lastdigit + 1))
				len1 += 1
			pos += 1
		return ans


import collections

class Solution:

	def jumpingNums(self, X):
		queue = collections.deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
		maxNum = float('-inf')
		while queue:
			num = queue.popleft()
			if num > X:
				continue
			maxNum = max(maxNum, num)
			nextNums = []
			digit = num % 10
			newDigits = []
			if digit == 0:
				newDigits = [1]
			elif digit == 9:
				newDigits = [8]
			else:
				newDigits = [digit - 1, digit + 1]
			for newDigit in newDigits:
				newNum = num * 10 + newDigit
				queue.append(newNum)
		return maxNum


class Solution:

	def jumpingNums(self, X):
		from collections import deque
		q = deque()
		for i in range(1, 10):
			q.append(i)
		ans = 0
		while q:
			cur = q.popleft()
			if cur > X:
				continue
			ans = max(ans, cur)
			last = int(cur % 10)
			if last != 0:
				q.append(cur * 10 + (last - 1))
			if last != 9:
				q.append(cur * 10 + (last + 1))
		return ans


from collections import deque

class Solution:

	def jumpingNums(self, X):
		if X <= 9:
			return X
		q = deque()
		for i in range(10):
			q.append(i)
		ans = 1
		while len(q):
			curr = q.popleft()
			if curr > X:
				continue
			ans = max(ans, curr)
			last_digit = curr % 10
			if last_digit != 0:
				q.append(curr * 10 + last_digit - 1)
			if last_digit != 9:
				q.append(curr * 10 + last_digit + 1)
		return ans


from collections import deque

class Solution:

	def jumpingNums(self, X):
		q = deque([i for i in range(10)])
		res = 0
		while q:
			num = q.popleft()
			if num > X:
				continue
			res = max(res, num)
			if num % 10 != 0:
				q.append(num * 10 + num % 10 - 1)
			if num % 10 != 9:
				q.append(num * 10 + num % 10 + 1)
		return res


def jump(l, c1, X, m):
	if len(l) == c1:
		a = int(''.join(l))
		if a <= X:
			m[0] = max(a, m[0])
		return
	if l[-1] != '9' and l[-1] != '-1':
		l.append(str(int(l[-1]) + 1))
		jump(l, c1, X, m)
		l.pop()
	if l[-1] != '0' and l[-1] != '-1':
		l.append(str(int(l[-1]) - 1))
		jump(l, c1, X, m)
		l.pop()

class Solution:

	def jumpingNums(self, X):
		if X <= 10:
			return X
		else:
			c1 = len(str(X))
			l = str(X)
			l1 = [0]
			l2 = [0]
			if l[0] == '1':
				jump(['9'], c1 - 1, X, l1)
			else:
				jump([str(int(l[0]) - 1)], c1, X, l1)
			jump([l[0]], c1, X, l2)
			return max(l1[0], l2[0])


class Solution:

	def jumpingNums(self, X):
		p = X
		arr = []
		while X:
			a = X % 10
			arr.append(a)
			X = X // 10
		arr.reverse()
		if len(arr) == 1:
			return p
		i = 1
		while i < len(arr) and abs(arr[i] - arr[i - 1]) == 1:
			i += 1
		if i == len(arr):
			return p
		if arr[i - 1] != 9 and arr[i - 1] + 1 < arr[i]:
			arr[i] = arr[i - 1] + 1
		elif arr[i - 1] != 0 and arr[i - 1] - 1 < arr[i]:
			arr[i] = arr[i - 1] - 1
		else:
			i -= 1
			while i > 0 and arr[i] < arr[i - 1]:
				i -= 1
			if i == 0:
				arr[i] -= 1
				if arr[i] == 0:
					arr[i + 1] = 9
					i += 1
			else:
				arr[i] -= 2
		for j in range(i + 1, len(arr)):
			if arr[j - 1] == 9:
				arr[j] = 8
			else:
				arr[j] = arr[j - 1] + 1
		ans = ''
		for x in arr:
			ans += str(x)
		return int(ans)


from collections import deque

class Solution:

	def jumpingNums(self, X):
		q = deque()
		for i in range(10):
			q.append(i)
		answer = 0
		while q:
			num = q.popleft()
			if num > X:
				continue
			answer = max(answer, num)
			ld = num % 10
			if ld != 0:
				first = num * 10 + (ld - 1)
				q.append(first)
			if ld != 9:
				second = num * 10 + (ld + 1)
				q.append(second)
		return answer


from collections import deque

class Solution:

	def jumpingNums(self, X):
		arr = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
		if X in range(10):
			return X
		else:
			last = 9
			while arr:
				ele = arr.popleft()
				if ele % 10 != 0 and ele % 10 != 9:
					new_ele_1 = ele * 10 + ele % 10 - 1
					new_ele_2 = ele * 10 + ele % 10 + 1
					if X >= new_ele_2:
						last = new_ele_2
						arr.extend([new_ele_1, new_ele_2])
					elif X >= new_ele_1:
						last = new_ele_1
						arr.append(new_ele_1)
					else:
						return last
				elif ele % 10 == 0:
					new_ele = ele * 10 + ele % 10 + 1
					if X >= new_ele:
						last = new_ele
						arr.append(new_ele)
					else:
						return last
				else:
					new_ele = ele * 10 + ele % 10 - 1
					if X >= new_ele:
						last = new_ele
						arr.append(new_ele)
					else:
						return last


from collections import deque as q

class Solution:

	def jumpingNums(self, X):

		def funk(x):
			ans = 0
			p = q([i for i in range(1, 10)])
			l = 9
			while l:
				s = p.popleft()
				l -= 1
				a = s * 10 + s % 10 + 1
				b = s * 10 + s % 10 - 1
				ans = max(ans, s)
				if s % 10 == 0:
					if a <= x:
						p.append(a)
						l += 1
				elif s % 10 == 9:
					if b <= x:
						l += 1
						p.append(b)
				else:
					if a <= x:
						p.append(a)
						l += 1
					if b <= x:
						l += 1
						p.append(b)
			return ans
		return funk(X)


class Solution:

	def jumpingNums(self, X):
		X = int(X)
		sx = str(X)
		if len(sx) == 1:
			return X
		is_valid = True
		for i in range(len(sx) - 1):
			if abs(int(sx[i]) - int(sx[i + 1])) != 1:
				is_valid = False
				break
		if is_valid:
			return X
		for i in range(len(sx) - 1):
			di0 = int(sx[i])
			di1 = int(sx[i + 1])
			if abs(di0 - di1) == 1:
				continue
			pre = sx[:i]
			post = '9' * (len(sx) - 2 - i)
			if di1 > di0:
				return self.jumpingNums(pre + sx[i] + str(di0 + 1) + post)
			elif di1 == di0:
				if di1 != 0:
					return self.jumpingNums(pre + sx[i] + str(di0 - 1) + post)
				else:
					return self.jumpingNums(pre[:-1] + str(int(sx[i - 1]) - 1) + '99' + post)
			elif di1 < di0:
				return self.jumpingNums(pre + str(di0 - 1) + '9' + post)
		return -1


from collections import deque

class Solution:

	def jumpingNums(self, X):
		q = deque()
		for i in range(1, 10):
			q.append(i)
		res = 0
		while q:
			n = q.popleft()
			if n > X:
				continue
			res = max(res, n)
			last = n % 10
			if last != 0:
				f = n * 10 + last - 1
				q.append(f)
			if last != 9:
				s = n * 10 + last + 1
				q.append(s)
		return res