Question
Here's the translation of the problem statement to English:
Alice the Rabbit solves math problems diligently, setting a target quantity. The target quantity is always an integer.
The number of math problems to solve tomorrow is the smallest number that is:
1. Larger than the number of problems solved today
2. Has the same digit composition as the number of problems solved today
For example, if 67 problems were solved today, then 76 problems will be solved the next day.
Write a program that takes the number of problems solved today as input and outputs the number of problems to be solved the next day.
my solution
can blindly just compute all permutations and sort and find the next biggest one but it is inefficient
official solution
https://logicmojo.com/next-greater-permutation
https://www.geeksforgeeks.org/next-permutation/
look at the images it is clear to understand
1) we first need to find an index (left) where there is an increasing trend of lst[index] and lst[index+1]
2) we find the smallest number that is bigger than our lst[left] to swap and assign right pointer to it
3) swap values at left and right indexes
4) reverse from lst[left+1:] onwards
The reverse is cuz while traversing our left pointer, we found out that it is all decreasing trend like if number is 14752, [left is 4]752. Since it is all decreasing, we want to swap to get increasing trend to make the number smaller.
complexity
o(n) time for offical
o n! * n for computing all permu
