package main
import (
"fmt"
"strconv"
)
// 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 slice
func NextGreaterNumber(n int64) int64 {
// Convert number to slice of digit runes
digits := []rune(strconv.FormatInt(n, 10))
length := len(digits)
// Step 1: Find pivot (first digit from right that is smaller than the next)
i := length - 2
for 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
j := length - 1
for j > i && digits[j] <= digits[i] {
j--
}
// Step 3: Swap pivot with that digit
digits[i], digits[j] = digits[j], digits[i]
// Step 4: Reverse the suffix (everything after pivot)
left, right := i+1, length-1
for left < right {
digits[left], digits[right] = digits[right], digits[left]
left++
right--
}
// Convert digits back to int64
result, _ := strconv.ParseInt(string(digits), 10, 64)
return result
}
func main() {
fmt.Println("Result:", NextGreaterNumber(534965)) // 535469
fmt.Println("-----------------------------")
fmt.Println("Result:", NextGreaterNumber(111)) // -1 (all digits identical)
fmt.Println("-----------------------------")
fmt.Println("Result:", NextGreaterNumber(7600)) // -1 (already the largest)
}
/*
run:
Result: 535469
-----------------------------
Result: -1
-----------------------------
Result: -1
*/
