Find smallest permutation under constraints
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a non-negative integer `n`, consider its decimal digits as a multiset (digits can repeat).
1) Return the **smallest possible integer** that can be formed by rearranging the digits of `n`, **allowing leading zeros** (i.e., you are allowed to place `0` at the front; the result is still treated as an integer value).
2) Follow-up: Given an additional integer `lowerBound`, return the **smallest integer strictly greater than `lowerBound`** that can be formed by rearranging the digits of `n`. If no such number exists, return an indication such as `-1`.
### Example
- `n = 178`: smallest permutation (allow leading zeros) is `178`.
- Follow-up: `n = 178`, `lowerBound = 200` → answer is `718`.
### Constraints
- You may assume `n` fits in 32-bit signed integer input, but intermediate permutations may exceed 32-bit; define how you handle overflow (e.g., use 64-bit or strings).
Quick Answer: This question evaluates digit-manipulation and combinatorial permutation skills, along with numeric ordering and representation concerns such as leading zeros and overflow handling in the Coding & Algorithms domain.
Part 1: Smallest Integer From Digit Rearrangement
Given a non-negative integer `n`, rearrange all of its decimal digits to form the smallest possible integer value. Leading zeros are allowed in the rearranged digit string, and those zeros are ignored when the value is interpreted as an integer. For example, rearranging `1002` as `0012` produces the integer `12`.
Constraints
- `0 <= n <= 2,147,483,647`
- `n` is given in base 10
- Leading zeros are allowed in the rearranged digit string
- Use normal Python integers for the result
Examples
Input: 178
Expected Output: 178
Explanation: The digits are already in ascending order, so the smallest rearrangement is 178.
Input: 1002
Expected Output: 12
Explanation: Sorting gives `0012`, which is interpreted as the integer 12.
Input: 9070
Expected Output: 79
Explanation: Sorting gives `0079`, which becomes 79 as an integer.
Input: 0
Expected Output: 0
Explanation: The only rearrangement of the single digit 0 is 0.