Given a number n, find the smallest number that has the same set of digits as n and is greater than n. If n is the greatest possible number with its set of digits, report it.
Example 1:
Input:
N = 143
Output: 314
Explanation: Numbers possible with digits
1, 3 and 4 are: 134, 143, 314, 341, 413, 431.
The first greater number after 143 is 314.
Example 2:
Input:
N = 431
Output: not possible
Explanation: Numbers possible with digits
1, 3 and 4 are: 134, 143, 314, 341, 413, 431.
Clearly, there's no number greater than 431.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findNext () which takes an integer N as input and returns the smallest number greater than N with the same set of digits as N. If such a number is not possible, return -1.
Expected Time Complexity: O(LogN).
Expected Auxiliary Space: O(LogN).
Constraints:
1 ≤ N ≤ 100000

Source: geeksforgeeks | Difficulty: EASY
Tags: Complete search

Starter code: #User function Template for python3



class Solution:

    def findNext (self,n):

        # your code here

Solutions:
class Solution:

	def findNext(self, num):
		s = []
		temp = num
		while temp > 0:
			k = temp % 10
			s.append(k)
			temp //= 10
		s = s[::-1]
		N = len(s)
		arr = s
		idx = N - 1
		for i in range(N - 2, -1, -1):
			if arr[i] < arr[i + 1]:
				idx = i
				break
		if idx == N - 1:
			return -1
		for i in range(idx + 1, N):
			if arr[idx] >= arr[i]:
				(arr[i - 1], arr[idx]) = (arr[idx], arr[i - 1])
				break
			elif i == N - 1:
				(arr[i], arr[idx]) = (arr[idx], arr[i])
		arr = arr[:idx + 1] + arr[N - 1:idx:-1]
		res = ''
		i = 0
		while i < len(arr):
			res += str(arr[i])
			i += 1
		return int(res)


from itertools import permutations

class Solution:

	def findNext(self, n):
		k = str(n)
		permutation = [''.join(p) for p in permutations(k)]
		p = permutation
		p = list(sorted(set(p)))
		if p[len(p) - 1] > k:
			return p[p.index(k) + 1]
		return -1


from itertools import permutations

class Solution:

	def findNext(self, n):
		num = list(str(n))
		num.sort()
		flag = 0
		p = permutations(num)
		for i in list(p):
			string = ''
			for j in i:
				string += j
			if int(string) > n:
				flag = 1
				break
		if flag:
			return int(string)
		return -1


from itertools import permutations

class Solution:

	def findNext(self, n):
		k = str(n)
		ans = list(permutations(k))
		ans.sort()
		lis = []
		for i in range(len(ans)):
			k = ''.join(ans[i])
			lis.append(int(k))
		lis = set(lis)
		lis = list(lis)
		lis.sort()
		if lis[-1] == n:
			return -1
		ind = lis.index(n)
		return lis[ind + 1]


from itertools import permutations

class Solution:

	def findNext(self, n):
		s = str(n)
		p = [''.join(p) for p in permutations(s)]
		k = [int(x) for x in p]
		v = list(set(k))
		v.sort()
		for i in range(0, len(v)):
			if v[i] == n and i < len(v) - 1:
				return v[i + 1]
			elif v[i] == n and i == len(v) - 1:
				return -1
			else:
				continue


class Solution:

	def findNext(self, N):
		number = [int(x) for x in str(N)]
		n = len(number)
		for i in range(n - 1, 0, -1):
			if number[i] > number[i - 1]:
				break
			if i == 1 and number[i] <= number[i - 1]:
				return -1
		x = number[i - 1]
		smallest = i
		for j in range(i + 1, n):
			if number[j] > x and number[j] < number[smallest]:
				smallest = j
		(number[smallest], number[i - 1]) = (number[i - 1], number[smallest])
		x = 0
		for j in range(i):
			x = x * 10 + number[j]
		number = sorted(number[i:])
		for j in range(n - i):
			x = x * 10 + number[j]
		return x


from itertools import permutations

class Solution:

	def findNext(self, n):
		items = [''.join(item) for item in set(permutations(str(n)))]
		items.sort()
		index = items.index(str(n))
		return items[index + 1] if index < len(items) - 1 else -1


class Solution:

	def findNext(self, n):
		s1 = str(n)
		l = len(s1)
		i = l - 2
		while i >= 0 and s1[i] >= s1[i + 1]:
			i -= 1
		if i == -1:
			return -1
		j = l - 1
		while s1[j] <= s1[i]:
			j -= 1
		s1 = list(s1)
		(s1[i], s1[j]) = (s1[j], s1[i])
		s1[i + 1:] = sorted(s1[i + 1:])
		return int(''.join(s1))


from heapq import heappop, heappush

class Solution:

	def findNext(self, n):
		digits = [int(x) for x in str(n)]
		l = len(digits)
		i = l - 1
		traversed = [digits[-1]]
		while i > 0 and digits[i] <= digits[i - 1]:
			heappush(traversed, digits[i - 1])
			i -= 1
		if i == 0:
			return -1
		else:
			curr_digit = digits[i - 1]
			smaller_nums = []
			popped = heappop(traversed)
			while curr_digit >= popped:
				smaller_nums.append(popped)
				popped = heappop(traversed)
			digits[i - 1] = popped
			heappush(traversed, curr_digit)
			k = i
			j = 0
			while j < len(smaller_nums):
				digits[k] = smaller_nums[j]
				k += 1
				j += 1
			while k < l:
				digits[k] = heappop(traversed)
				k += 1
		num = 0
		for j in range(l):
			num = num * 10 + digits[j]
		return num


from itertools import permutations

class Solution:

	def findNext(self, n):
		b = n
		j = str(n)
		r = [''.join(p) for p in permutations(j)]
		q = list(map(int, r))
		q = sorted(q)
		v = []
		for s in range(len(q)):
			if q[s] > b:
				v.append(q[s])
		v = sorted(v)
		if len(v) == 0:
			return 'not possible'
		else:
			return v[0]


class Solution:

	def binarysearch(self, arr, l, r, k):
		if l <= r:
			mid = (l + r) // 2
			if int(arr[mid]) > k:
				return self.binarysearch(arr, mid + 1, r, k)
			else:
				return self.binarysearch(arr, l, mid - 1, k)
		return r

	def findNext(self, n):
		n = str(n)
		n1 = n
		ind = None
		for i in range(len(n) - 2, -1, -1):
			if int(n[i]) < int(n[i + 1]):
				ind = i
				break
		if ind == None:
			return -1
		arr = list(n[ind + 1:len(n)])
		ind2 = self.binarysearch(n, ind + 1, len(n) - 1, int(n[ind]))
		n = list(n)
		(n[ind], n[ind2]) = (n[ind2], n[ind])
		n[ind + 1:len(n)] = n[ind + 1:len(n)][::-1]
		s = ''.join(n)
		if s == n1:
			return -1
		return int(s)


class Solution:

	def findNext(self, n):
		n = list(str(n))
		n_len = len(n)
		vBreakIndex = -1
		for j in range(n_len - 2, -1, -1):
			if n[j] < n[j + 1]:
				vBreakIndex = j
				break
		if vBreakIndex == -1:
			return -1
		for j in range(n_len - 1, vBreakIndex - 1, -1):
			if n[j] > n[vBreakIndex]:
				(n[j], n[vBreakIndex]) = (n[vBreakIndex], n[j])
				break
		n[vBreakIndex + 1:] = sorted(n[vBreakIndex + 1:])
		outElement = 0
		vMult = 1
		for j in range(n_len - 1, -1, -1):
			outElement = outElement + int(n[j]) % 10 * vMult
			vMult *= 10
		return outElement


class Solution:

	def findNext(self, n):
		ind1 = -1
		arr = list(map(int, str(n)))
		length = len(arr)
		for i in range(length - 2, -1, -1):
			if arr[i] < arr[i + 1]:
				ind1 = i
				break
		if ind1 == -1:
			return -1
		ind2 = -1
		for i in range(length - 1, -1, -1):
			if arr[i] > arr[ind1]:
				ind2 = i
				break
		(arr[ind1], arr[ind2]) = (arr[ind2], arr[ind1])
		start = ind1 + 1
		end = length - 1
		while start < end:
			(arr[start], arr[end]) = (arr[end], arr[start])
			start += 1
			end -= 1
		news = 0
		for i in arr:
			news = news * 10 + i
		return news


class Solution:

	def findNext(self, n):
		str_n = str(n)
		for ind in range(len(str_n) - 1, 0, -1):
			if str_n[ind] > str_n[ind - 1]:
				str_n = list(str_n)
				(smallest, j) = (ind, ind + 1)
				while j < len(str_n):
					if str_n[j] > str_n[ind - 1] and str_n[j] < str_n[smallest]:
						smallest = j
					j += 1
				(str_n[smallest], str_n[ind - 1]) = (str_n[ind - 1], str_n[smallest])
				str_n[ind:] = sorted(str_n[ind:])
				return int(''.join(str_n))
		return -1


class Solution:

	def findNext(self, x1):
		num = str(x1)
		number = []
		for i in num:
			number.append(i)
		n = len(number)
		for i in range(n - 1, 0, -1):
			if number[i] > number[i - 1]:
				break
		if i == 1 and number[i] <= number[i - 1]:
			return 'not possible'
		x = number[i - 1]
		smallest = i
		for j in range(i + 1, n):
			if number[j] > x and number[j] < number[smallest]:
				smallest = j
		(number[smallest], number[i - 1]) = (number[i - 1], number[smallest])
		x = 0
		for j in range(i):
			x = x * 10 + int(number[j])
		number = sorted(number[i:])
		for j in range(n - i):
			x = x * 10 + int(number[j])
		return x


class Solution:

	def findNext(self, n):
		arr = []
		temp = n
		while temp > 0:
			arr.append(temp % 10)
			temp = temp // 10
		arr = arr[::-1]
		idx1 = -1
		idx2 = -1
		for i in range(len(arr) - 2, -1, -1):
			if arr[i] < arr[i + 1]:
				idx1 = i
				break
		if idx1 == -1:
			return -1
		for i in range(len(arr) - 1, idx1, -1):
			if arr[i] > arr[idx1]:
				idx2 = i
				break
		(arr[idx1], arr[idx2]) = (arr[idx2], arr[idx1])
		arr[idx1 + 1:len(arr)] = arr[len(arr) - 1:idx1:-1]
		res = ''
		i = 0
		while i < len(arr):
			res += str(arr[i])
			i += 1
		return int(res)


class Solution:

	def findNext(self, n):
		n = list(map(int, str(n)))
		k = 0
		for i in range(len(n) - 1, -1, -1):
			if n[i] > n[i - 1]:
				k = i
				break
		if k == 0:
			return -1
		w = k
		for j in range(len(n) - 1, i, -1):
			if n[j] > n[k - 1]:
				w = j
				break
		(n[k - 1], n[w]) = (n[w], n[k - 1])
		n[k:] = sorted(n[k:])
		return int(''.join(map(str, n)))


class Solution:

	def findNext(self, n):
		kk = str(n)
		from itertools import permutations
		d = list(kk)
		p = permutations(d, len(d))
		res = []
		for i in list(p):
			res.append(i)
		res = [int(''.join(i)) for i in res]
		for i in res:
			if i < n:
				res.remove(i)
		res.remove(n)
		res = sorted(res)
		for i in res:
			if i > n:
				return i
				break
		return 'not possible'


class Solution:

	def findNext(self, n):
		ind = -1
		arr = [i for i in str(n)]
		x = len(arr)
		if x == 1:
			return -1
		for i in range(x - 2, -1, -1):
			if arr[i] < arr[i + 1]:
				ind = i
				break
		if ind == -1:
			return ind
		for i in range(x - 1, ind, -1):
			if arr[i] > arr[ind]:
				(arr[i], arr[ind]) = (arr[ind], arr[i])
				break
		i = ind + 1
		j = x - 1
		while i < j:
			(arr[i], arr[j]) = (arr[j], arr[i])
			i += 1
			j -= 1
		return int(''.join([x for x in arr]))


from itertools import permutations

class Solution:

	def findNext(self, n):
		s = tuple(str(n))
		x = list(dict.fromkeys(permutations(s)))
		x.sort()
		try:
			ans = x.index(s)
			an = x[ans + 1]
			su = ''
			for i in range(0, len(an)):
				su += an[i]
			return int(su)
		except:
			return -1


class Solution:

	def nextP(self, N, arr):
		p = 0
		for i in range(N - 1, 0, -1):
			if arr[i - 1] < arr[i]:
				p = i
				break
		if p == 0:
			return -1
		k = N - 1
		while arr[p - 1] >= arr[k]:
			k = k - 1
		(arr[p - 1], arr[k]) = (arr[k], arr[p - 1])
		i = p
		k = N - 1
		while i < k:
			(arr[i], arr[k]) = (arr[k], arr[i])
			i += 1
			k -= 1
		return ''.join(arr)

	def findNext(self, n):
		a = []
		for i in n:
			a.append(i)
		return self.nextP(len(a), a)


from itertools import permutations

class Solution:

	def findNext(self, n):
		s = str(n)
		res = [''.join(p) for p in permutations(s)]
		x = []
		for i in res:
			if int(i) > n:
				x.append(i)
		x.sort()
		if not x:
			return 'not possible'
		else:
			return x[0]


class Solution:

	def findNext(self, n):
		value = n
		number = list(map(int, str(n)))
		n = len(str(n))
		for i in range(n - 1, 0, -1):
			if number[i] > number[i - 1]:
				break
		if i == 1 and number[i] <= number[i - 1]:
			a = 'not possible'
			return a
		x = number[i - 1]
		smallest = i
		for j in range(i + 1, n):
			if number[j] > x and number[j] < number[smallest]:
				smallest = j
		(number[smallest], number[i - 1]) = (number[i - 1], number[smallest])
		x = 0
		for j in range(i):
			x = x * 10 + number[j]
		number = sorted(number[i:])
		for j in range(n - i):
			x = x * 10 + number[j]
		return x


from bisect import bisect_right as br

class Solution:

	def findNext(self, n):
		bla = n

		def rec(ans, arr, temp):
			if len(arr) > 1:
				for i in range(len(arr)):
					tem = temp.copy()
					tem += arr[i]
					temparr = arr.copy()
					del temparr[i]
					rec(ans, temparr, tem)
			else:
				temp.append(arr[0])
				ans.append(temp)
		n = str(n)
		arr = list(n)
		ans = []
		temp = []
		rec(ans, arr, temp)
		final = []
		for ele in ans:
			temp = int(''.join(ele))
			final.append(temp)
		final.sort()
		if final[-1] == bla:
			return -1
		else:
			ind = br(final, bla)
			return final[ind]


class Solution:

	def findNext(self, n):

		def print(s, ans, ind):
			if ind == len(s):
				k = ''.join(s)
				ans.add(int(k))
				return
			else:
				for i in range(ind, len(s)):
					(s[i], s[ind]) = (s[ind], s[i])
					print(s, ans, ind + 1)
					(s[i], s[ind]) = (s[ind], s[i])
		s = list(str(n))
		ans = set()
		index = 0
		print(s, ans, index)
		ans = list(ans)
		ans.sort()
		i = ans.index(n)
		if ans[-1] == n:
			return -1
		return ans[i + 1]


class Solution:

	def findNext(self, n):

		def recurs(a, ans, ind):
			if ind == len(a):
				k = ''.join(a)
				ans.add(int(k))
			for i in range(ind, len(a)):
				(a[ind], a[i]) = (a[i], a[ind])
				recurs(a, ans, ind + 1)
				(a[ind], a[i]) = (a[i], a[ind])
		a = list(str(n))
		ans = set()
		recurs(a, ans, 0)
		ans = list(ans)
		ans.sort()
		i = ans.index(n)
		if ans[-1] == n:
			return -1
		return ans[i + 1]


class Solution:

	def findNext(self, n):
		arr = []
		for i in str(n):
			arr.append(int(i))
		m = len(arr)
		f = 0
		for i in range(m - 1, 0, -1):
			if arr[i] > arr[i - 1]:
				arr[i:] = sorted(arr[i:])
				for j in range(i, m):
					if arr[j] > arr[i - 1]:
						(arr[i - 1], arr[j]) = (arr[j], arr[i - 1])
						break
				f = 1
				break
		if f == 0:
			return -1
		ans = ''
		for i in arr:
			ans += str(i)
		return ans


class Solution:

	def bin_search(self, beg, end, val, s):
		while beg <= end:
			mid = beg + (end - beg) // 2
			if int(s[mid]) > val:
				beg = mid + 1
			else:
				end = mid - 1
		return end

	def findNext(self, num):
		s = str(num)
		n = len(s)
		ind = -1
		final_str = ' '
		for i in range(n - 2, -1, -1):
			if s[i] >= s[i + 1]:
				continue
			else:
				ind = i
				break
		if ind == -1:
			return -1
		swap_ind = self.bin_search(ind + 1, n - 1, int(s[ind]), s)
		swapped_val = s[swap_ind]
		sorted_str = ''
		for i in range(n - 1, ind, -1):
			if i == swap_ind:
				sorted_str = sorted_str + s[ind]
				continue
			sorted_str = sorted_str + s[i]
		final_str = s[:ind] + s[swap_ind] + sorted_str
		return final_str


from collections import Counter

class Solution:

	def findNext(self, d):
		t = str(d)
		cnt = Counter(t)
		for i in range(d + 1, pow(10, len(t))):
			cnt1 = Counter(str(i))
			if cnt == cnt1:
				return i
		return -1


class Solution:

	def findNext(self, n):
		arr = []
		while n > 0:
			arr.append(n % 10)
			n = n // 10
		arr = arr[::-1]
		i = len(arr) - 2
		while i >= 0 and arr[i] >= arr[i + 1]:
			i -= 1
		if i == -1:
			return -1
		k = len(arr) - 1
		while arr[i] >= arr[k]:
			k -= 1
		temp = arr[i]
		arr[i] = arr[k]
		arr[k] = temp
		res = 0
		for j in range(i + 1):
			res = res * 10 + arr[j]
		for j in range(len(arr) - 1, i, -1):
			res = res * 10 + arr[j]
		return res


from itertools import permutations

class Solution:

	def findNext(self, n):
		k = str(n)
		permutation = [''.join(p) for p in permutations(k)]
		p = permutation
		p = list(sorted(set(p)))
		if p[len(p) - 1] > k:
			return p[p.index(k) + 1]
		return -1
t = int(input())
for tc in range(t):
	n = int(input())
	ob = Solution()
	res = ob.findNext(n)
	if res == -1:
		print('not possible')
	else:
		print(res)


from itertools import permutations

class Solution:

	def findNext(self, n):
		b = n
		j = str(n)
		r = [''.join(p) for p in permutations(j)]
		q = list(map(int, r))
		q = sorted(q)
		v = []
		for s in range(len(q)):
			if q[s] > b:
				v.append(q[s])
		v = sorted(v)
		if len(v) == 0:
			return 'not possible'
		else:
			return v[0]
t = int(input())
for tc in range(t):
	n = int(input())
	ob = Solution()
	res = ob.findNext(n)
	if res == -1:
		print('not possible')
	else:
		print(res)


class Solution:

	def findNext(self, num):
		s = []
		temp = num
		while temp > 0:
			k = temp % 10
			s.append(k)
			temp //= 10
		s = s[::-1]
		N = len(s)
		arr = s
		idx = N - 1
		for i in range(N - 2, -1, -1):
			if arr[i] < arr[i + 1]:
				idx = i
				break
		if idx == N - 1:
			return -1
		for i in range(idx + 1, N):
			if arr[idx] >= arr[i]:
				(arr[i - 1], arr[idx]) = (arr[idx], arr[i - 1])
				break
			elif i == N - 1:
				(arr[i], arr[idx]) = (arr[idx], arr[i])
		arr = arr[:idx + 1] + arr[N - 1:idx:-1]
		res = ''
		i = 0
		while i < len(arr):
			res += str(arr[i])
			i += 1
		return int(res)
t = int(input())
for tc in range(t):
	n = int(input())
	ob = Solution()
	res = ob.findNext(n)
	if res == -1:
		print('not possible')
	else:
		print(res)


from itertools import permutations

class Solution:

	def findNext(self, n):
		n = str(n)
		digits = [i for i in n]
		numbers = permutations(digits)
		greater_nums = []
		for num in numbers:
			a = ''.join(num)
			n = int(n)
			a = int(a)
			if a > n:
				greater_nums.append(a)
		if greater_nums:
			mn = greater_nums[0]
			for i in greater_nums[1:]:
				if i < mn:
					mn = i
			return mn
		else:
			return -1
t = int(input())
for tc in range(t):
	n = int(input())
	ob = Solution()
	res = ob.findNext(n)
	if res == -1:
		print('not possible')
	else:
		print(res)


class Solution:

	def findNext(self, n):
		st = list(str(n))
		lt = len(st) - 1
		(st1, st2) = (None, None)
		while lt > 0:
			x = lt - 1
			while x >= 0:
				if st[x] < st[lt]:
					if st1 == None or (st1 != None and x > st1):
						(st1, st2) = (x, lt)
						break
				x -= 1
			lt -= 1
		if st1 == None and st2 == None:
			return -1
		(st[st1], st[st2]) = (st[st2], st[st1])
		st = st[:st1 + 1] + sorted(st[st1 + 1:])
		return int(''.join(st))
t = int(input())
for tc in range(t):
	n = int(input())
	ob = Solution()
	res = ob.findNext(n)
	if res == -1:
		print('not possible')
	else:
		print(res)


from itertools import permutations

class Solution:

	def findNext(self, n):
		a = str(n)
		d = list(a)
		p = permutations(d, len(d))
		res = []
		for i in list(p):
			res.append(i)
		res = [int(''.join(i)) for i in res]
		res.sort()
		x = res.index(n)
		if res[len(res) - 1] == n:
			return -1
		for i in range(x + 1, len(res)):
			if res[i] > n:
				return res[i]


class Solution:

	def findNext(self, n):
		k = n
		l = []
		while n > 0:
			l.append(n % 10)
			n //= 10
		len1 = len(l)
		p = []
		p.append(l[0])
		z = -1
		min1 = 100
		for i in range(1, len1):
			if l[i] < l[i - 1]:
				for it in p:
					if it < min1 and it > l[i]:
						min1 = it
				p.remove(min1)
				p.append(l[i])
				z = i
				break
			else:
				p.append(l[i])
		if z == -1:
			return -1
		else:
			y = len(p)
			p.sort()
			c = ''
			c += str(min1)
			for t in p:
				c += str(t)
			ans = ''
			for k in range(len1 - 1, y, -1):
				ans += str(l[k])
			ans += c
			ans1 = int(ans)
			return ans1


class Solution:

	def findNext(self, n):
		nums = [val for val in str(n)]
		n = len(nums)
		if n == 1:
			return nums[0]
		for i in range(n - 2, -1, -1):
			if nums[i] < nums[i + 1]:
				break
		if i == 0 and nums[i] >= nums[i + 1]:
			return -1
		for j in range(n - 1, i, -1):
			if nums[j] > nums[i]:
				break
		(nums[j], nums[i]) = (nums[i], nums[j])
		i += 1
		j = n - 1
		while i <= j:
			(nums[j], nums[i]) = (nums[i], nums[j])
			j -= 1
			i += 1
		return ''.join(nums)


class Solution:

	def findNext(self, n):
		(s, x, a, b) = (str(n), '', -1, -1)
		z = len(s)
		for i in range(z - 2, -1, -1):
			if s[i] < s[i + 1]:
				a = i
				break
		if a == -1:
			return -1
		for i in range(z - 1, -1, -1):
			if s[i] > s[a]:
				b = i
				break
		x += s[:a]
		x += s[b]
		x += s[b + 1:][::-1]
		x += s[a]
		x += s[a + 1:b][::-1]
		return x


class Solution:

	def findNext(self, n):
		a = []
		for dig in str(n):
			a.append(dig)
		l = len(a)
		k = l - 2
		while k >= 0:
			if int(a[k]) < int(a[k + 1]):
				break
			k -= 1
		if k < 0:
			return -1
		else:
			for i in range(l - 1, k, -1):
				if int(a[i]) > int(a[k]):
					break
			(a[i], a[k]) = (a[k], a[i])
			a[k + 1:] = reversed(a[k + 1:])
		return int(''.join(a))


class Solution:

	def findNext(self, n):
		n = list(str(n))
		if n == sorted(n, reverse=True):
			return -1
		for i in range(len(n) - 2, -1, -1):
			if n[i] < n[i + 1]:
				break
		left = n[:i]
		right = n[i + 1:]
		d = [n[i]]
		minn = 1000000000.0
		for (i, j) in enumerate(right):
			if j > d[0]:
				if int(j) < minn:
					minn = int(j)
					swap_i = i
		(d[0], right[swap_i]) = (right[swap_i], d[0])
		res = left + d + sorted(right)
		return ''.join(res)


class Solution:

	def findNext(self, integer):
		lis = list(str(integer))
		n = len(lis)
		i = n - 1
		while i > 0 and lis[i - 1] >= lis[i]:
			i -= 1
		if i == 0:
			return -1
		ind = i - 1
		mn_ind = i
		for j in range(i, n):
			if lis[j] > lis[ind] and lis[j] < lis[mn_ind]:
				mn_ind = j
		(lis[i - 1], lis[mn_ind]) = (lis[mn_ind], lis[i - 1])
		res = ''.join(lis[:i])
		rem = lis[i:]
		rem.sort()
		rem = ''.join(rem)
		return int(res + rem)


class Solution:

	def findNext(self, n):
		arr = [i for i in str(n)]
		z = len(arr)
		ind = -1
		for i in range(z - 2, -1, -1):
			if arr[i] < arr[i + 1]:
				ind = i
				break
		if ind == -1:
			return -1
		gInd = -1
		for i in range(z - 1, ind, -1):
			if arr[i] > arr[ind]:
				gInd = i
				break
		(arr[ind], arr[gInd]) = (arr[gInd], arr[ind])
		(b, c) = (ind + 1, z - 1)
		while b < c:
			(arr[b], arr[c]) = (arr[c], arr[b])
			b += 1
			c -= 1
		return int(''.join([x for x in arr]))


class Solution:

	def findNext(self, n):
		n = str(n)
		l = []
		for x in range(0, len(n)):
			l.append(n[x])
		if l == sorted(l, reverse=True):
			return -1
		for x in range(len(n) - 1, 0, -1):
			if l[x] > l[x - 1]:
				a = l[x - 1]
				m = l[x]
				i = x
				for y in range(x + 1, len(l)):
					if m > l[y] and l[y] > a:
						m = l[y]
						i = y
				(l[x - 1], l[i]) = (l[i], l[x - 1])
				p = sorted(l[x:])
				for y in range(0, len(p)):
					l[x + y] = p[y]
				break
		n = ''.join(l)
		n = int(n)
		return n


class Solution:

	def findNext(self, n):
		num = [l for l in str(n)]
		j = len(num) - 1
		smallerDigitIndex = -1
		for z in range(j - 1, -1, -1):
			if num[z] < num[z + 1]:
				smallerDigitIndex = z
				break
		if smallerDigitIndex == -1:
			return -1
		else:
			for k in range(j, smallerDigitIndex, -1):
				if num[k] > num[smallerDigitIndex]:
					(num[k], num[smallerDigitIndex]) = (num[smallerDigitIndex], num[k])
					break
			(b, c) = (smallerDigitIndex + 1, j)
			while b < c:
				(num[b], num[c]) = (num[c], num[b])
				b += 1
				c -= 1
			return int(''.join([x for x in num]))


class Solution:

	def findNext(self, n):
		s = list(str(n))
		for i in range(len(s) - 1, 0, -1):
			if s[i] > s[i - 1]:
				break
			if i == 1:
				return -1
		x = i - 1
		smallest = i
		for j in range(i + 1, len(s)):
			if s[j] > s[x] and s[j] < s[smallest]:
				smallest = j
		(s[x], s[smallest]) = (s[smallest], s[x])
		s[i:] = sorted(s[i:])
		return int(''.join(s))


class Solution:

	def findNext(self, n):
		l = list(str(n))
		cur = -1
		for i in range(len(l) - 1, 0, -1):
			if l[i - 1] < l[i]:
				cur = i
				break
		if cur == -1:
			return -1
		ele = l[cur - 1]
		(smallest_bigger, smallest_bigger_ind) = (l[-1], -1)
		for i in range(len(l) - 1, cur - 1, -1):
			if l[i] > ele:
				(smallest_bigger, smallest_bigger_ind) = (l[i], i)
				break
		(l[cur - 1], l[smallest_bigger_ind]) = (smallest_bigger, ele)
		return int(''.join(l[:cur] + sorted(l[cur:])))


from itertools import permutations

class Solution:

	def findNext(self, n):
		k = str(n)
		z = list(permutations(k))
		L = []
		for i in z:
			s = ''.join(i)
			L.append(s)
		L.sort()
		for j in L:
			if int(j) > n:
				return j
		else:
			return 'not possible'


class Solution:

	def findNext(self, n):
		n = list(str(n))
		sortedNum = ''.join(sorted(n, reverse=True))
		num = ''.join(n)
		if num == sortedNum or len(set(list(str(n)))) == 1:
			return 'not possible'
		else:
			for i in range(len(n) - 2, -1, -1):
				if n[i] < n[i + 1]:
					d = i
					break
			target1 = n[d]
			mark = n[d + 1]
			flag = 0
			for i in range(d + 1, len(n)):
				if target1 < n[i]:
					flag = 1
					mark = min(mark, n[i])
					pos = i
			if flag == 0:
				return 'not possible'
			(n[d], n[pos]) = (n[pos], n[d])
			n = n[0:d + 1] + sorted(n[d + 1:])
			return ''.join(n)


class Solution:

	def findNext(self, n):
		str_num = str(n)
		digits_count = {i: 0 for i in str_num}
		for i in str_num:
			digits_count[i] += 1
		num_length = len(str_num)
		max_digit = str(int(max(str_num)) + 1)
		maxnum = max_digit
		for i in range(num_length - 1):
			maxnum += '0'
		for i in range(n, int(maxnum)):
			s = str(i)
			if str_num != s:
				digits_count2 = {i: 0 for i in s}
				for i in s:
					digits_count2[i] += 1
					if digits_count2 == digits_count:
						return s
		return -1


class Solution:

	def findNext(self, p):
		n = list(str(p))
		key = [int(n[-1])]
		m = int(n[-1])
		for i in range(len(n) - 2, -1, -1):
			if int(n[i]) >= m:
				m = int(n[i])
				key.append(int(n[i]))
			else:
				key.sort()
				for j in key:
					if j > int(n[i]):
						tt = n[i + 1:]
						tt.append(n[i])
						n[i] = str(j)
						tt.remove(str(j))
						tt.sort()
						n[i + 1:] = tt[:]
						break
				break
		n = int(''.join(n))
		if n == p:
			return -1
		return n


class Solution:

	def findNext(self, p):
		n = list(str(p))
		l = dict()
		l[int(n[-1])] = len(n) - 1
		m = int(n[-1])
		for i in range(len(n) - 2, -1, -1):
			if int(n[i]) >= m:
				m = int(n[i])
				l[m] = i
			else:
				key = list(l.keys())
				key.sort()
				for j in key:
					if j > int(n[i]):
						t = n[i]
						n[i] = str(j)
						tt = n[i + 1:] + [t]
						tt.remove(str(j))
						tt.sort()
						y = 0
						for r in range(i + 1, len(n)):
							n[r] = tt[y]
							y += 1
						break
				break
		n = int(''.join(n))
		if n == p:
			return -1
		return n


from itertools import permutations

class Solution:

	def findNext(self, n):
		con = str(n)
		per = [''.join(i) for i in permutations(con)]
		per = list(sorted(set(per)))
		if per[len(per) - 1] > con:
			return per[per.index(con) + 1]
		return -1


class Solution:

	def findNext(self, n):
		s = str(n)
		arr = list(s)
		l = len(s)
		k = l - 2
		while k >= 0:
			if arr[k] < arr[k + 1]:
				break
			k -= 1
		if k < 0:
			return -1
		else:
			for t in range(l - 1, k, -1):
				if arr[t] > arr[k]:
					break
			(arr[t], arr[k]) = (arr[k], arr[t])
			arr[k + 1:] = reversed(arr[k + 1:])
		ans = ''
		for i in arr:
			ans += i
		return int(ans)


class Solution:

	def findNext(self, n):
		arr = list(str(n))
		lenN = len(arr)
		vFlag = False
		for i in range(lenN - 2, -1, -1):
			if arr[i] < arr[i + 1]:
				vFlag = True
				break
		if vFlag == False:
			return -1
		else:
			for j in range(lenN - 1, i, -1):
				if arr[j] > arr[i]:
					(arr[i], arr[j]) = (arr[j], arr[i])
					break
			arr[i + 1:] = sorted(arr[i + 1:])
			return ''.join(arr)


class Solution:

	def findNext(self, n):
		a = list(str(n))
		i = len(a) - 1
		while i > 0 and a[i - 1] >= a[i]:
			i -= 1
		if i == 0:
			return -1
		j = len(a) - 1
		k = i - 1
		while a[k] >= a[j]:
			j -= 1
		(a[j], a[k]) = (a[k], a[j])
		r = len(a) - 1
		while i < r:
			(a[i], a[r]) = (a[r], a[i])
			i += 1
			r -= 1
		return int(''.join(a))


import itertools as it

class Solution:

	def findNext(self, n):
		l = []
		for i in str(n):
			l.append(int(i))
		a = list(it.permutations(l))
		b = []
		for i in a:
			list2 = list(i)
			list2 = map(str, list2)
			temp = ''.join(list2)
			b.append(int(temp))
		b.sort()
		for j in b:
			if j > n:
				return j
		else:
			return -1


from itertools import permutations

class Solution:

	def findNext(self, n):
		digits = []
		l = len(str(n))
		for i in str(n):
			digits.append(i)
		lists = sorted([int(''.join(list(i))) for i in list(permutations(digits, l))])
		for i in lists:
			if i > n:
				return i
		else:
			return 'not possible'


class Solution:

	def findNext(self, n):
		A = list(str(n))
		if len(A) <= 1:
			return n
		k = len(A) - 2
		while k >= 0:
			if int(A[k]) < int(A[k + 1]):
				break
			k -= 1
		if k < 0:
			return -1
		else:
			for i in range(len(A) - 1, k, -1):
				if int(A[i]) > int(A[k]):
					(A[i], A[k]) = (A[k], A[i])
					break
			A[k + 1:] = reversed(A[k + 1:])
			N = int(''.join(A))
			return N


class Solution:

	def findNext(self, n):
		from itertools import permutations
		digits = sorted([int(''.join(numbers)) for numbers in permutations(str(n))])
		for i in digits:
			if i > n:
				return i
		return -1


from itertools import permutations

class Solution:

	def findNext(self, n):
		n = str(n)
		L = list(permutations(n))
		L = [''.join(x) for x in L]
		L = [int(x) for x in L]
		L.sort()
		n = int(n)
		for x in L:
			if x > n:
				return x
		return -1


from itertools import permutations

class Solution:

	def findNext(self, n):
		perms = [int(''.join(p)) for p in permutations(str(n))]
		perms = list(set(perms))
		perms.sort()
		t = perms.index(n)
		if t == len(perms) - 1:
			return -1
		else:
			return perms[perms.index(n) + 1]


class Solution:

	def findNext(self, n):
		arr2 = list(str(n))
		arr2.sort()
		arr = list(str(n))
		i = len(arr) - 1
		while i > 0 and arr[i - 1] >= arr[i]:
			i -= 1
		arr[i:] = sorted(arr[i:])
		if i != 0:
			q = i
			while arr[i - 1] >= arr[q]:
				q += 1
			(arr[i - 1], arr[q]) = (arr[q], arr[i - 1])
		s = ''
		for i in arr:
			s += i
		s = int(s)
		if arr == arr2:
			return -1
		else:
			return s


class Solution:

	def nextPermutation(self, arr):
		n = len(arr)
		k = n - 2
		while k >= 0:
			if arr[k] < arr[k + 1]:
				break
			k -= 1
		if k < 0:
			arr = arr[::-1]
		else:
			for l in range(n - 1, k, -1):
				if arr[l] > arr[k]:
					break
			(arr[l], arr[k]) = (arr[k], arr[l])
			arr[k + 1:] = reversed(arr[k + 1:])
		return arr

	def findNext(self, n):
		n = str(n)
		arr = []
		for c in n:
			arr.append(int(c))
		result = self.nextPermutation(arr)
		num = ''.join([str(c) for c in result])
		if int(n) >= int(num):
			return -1
		return num


from itertools import permutations

class Solution:

	def findNext(self, n):
		k = [i for i in str(n)]
		c = list(permutations(k, len(str(n))))
		j = [''.join(list(i)) for i in c]
		j.sort()
		for i in j:
			if n < int(i):
				return i
		return -1