import Foundation
/// 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
func nextGreaterNumber(_ n: Int) -> Int {
// Convert number to array of digit characters
var digits = Array(String(n))
let length = digits.count
// 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
digits.swapAt(i, j)
// Step 4: Reverse the suffix (everything after pivot)
var left = i + 1
var right = length - 1
while left < right {
digits.swapAt(left, right)
left += 1
right -= 1
}
// Convert digits back to Int
return Int(String(digits)) ?? -1
}
// Test cases
print("Result:", nextGreaterNumber(534965)) // 535469
print("-----------------------------")
print("Result:", nextGreaterNumber(111)) // -1 (all digits identical)
print("-----------------------------")
print("Result:", nextGreaterNumber(7600)) // -1 (already the largest)
/*
run:
Result: 535469
-----------------------------
Result: -1
-----------------------------
Result: -1
*/
