object NextGreaterNumber {
/**
* 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
*/
def nextGreaterNumber(n: Long): Long = {
// Convert number to a mutable array of digit characters
val digits: Array[Char] = n.toString.toCharArray
val length = digits.length
// 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 -= 1
}
// 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 -= 1
}
// 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 += 1
right -= 1
}
// Convert digits back to Long
digits.mkString.toLong
}
def main(args: Array[String]): Unit = {
println(s"Result: ${nextGreaterNumber(534965)}") // 535469
println("-----------------------------")
println(s"Result: ${nextGreaterNumber(111)}") // -1 (all digits identical)
println("-----------------------------")
println(s"Result: ${nextGreaterNumber(7600)}") // -1 (already the largest)
}
}
/*
run:
Result: 535469
-----------------------------
Result: -1
-----------------------------
Result: -1
*/
