/**
* Finds the smallest number greater than `n`
* using exactly the same digits.
*
* Time Complexity: O(n)
* - One pass from right to left to find pivot
* - One pass from right to left to find swap candidate
* - One reverse of suffix
* Space Complexity: O(n) for digit array
*/
fun nextGreaterNumber(n: Long): Long {
// Convert number to mutable list of digit characters
val digits = n.toString().toMutableList()
val length = digits.size
// Step 1: Find pivot (first digit from right that is smaller than the next)
var i = length - 2
while (i >= 0 && digits[i] >= digits[i + 1]) {
i--
}
// If no pivot found → digits are in descending order → no larger number possible
if (i < 0) {
return -1
}
// Step 2: Find smallest digit to the right of pivot that is larger than pivot
var j = length - 1
while (j > i && digits[j] <= digits[i]) {
j--
}
// Step 3: Swap pivot with that digit
val temp = digits[i]
digits[i] = digits[j]
digits[j] = temp
// Step 4: Reverse the suffix (everything after pivot)
var left = i + 1
var right = length - 1
while (left < right) {
val t = digits[left]
digits[left] = digits[right]
digits[right] = t
left++
right--
}
// Convert digits back to Long
return digits.joinToString("").toLong()
}
fun main() {
println("Result: ${nextGreaterNumber(534965)}") // 535469
println("-----------------------------")
println("Result: ${nextGreaterNumber(111)}") // -1 (all digits identical)
println("-----------------------------")
println("Result: ${nextGreaterNumber(7600)}") // -1 (already the largest)
}
/*
run:
Result: 535469
-----------------------------
Result: -1
-----------------------------
Result: -1
*/
