/// 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 vector
fn next_greater_number(n: i64) -> i64 {
// Convert number to vector of digit chars
let mut digits: Vec<char> = n.to_string().chars().collect();
let length = digits.len();
// Step 1: Find pivot (first digit from right that is smaller than the next)
let mut i: isize = length as isize - 2;
while i >= 0 && digits[i as usize] >= digits[(i + 1) as usize] {
i -= 1;
}
// If no pivot found → digits are in descending order → no larger number possible
if i < 0 {
return -1;
}
let pivot = i as usize;
// Step 2: Find smallest digit to the right of pivot that is larger than pivot
let mut j = length - 1;
while j > pivot && digits[j] <= digits[pivot] {
j -= 1;
}
// Step 3: Swap pivot with that digit
digits.swap(pivot, j);
// Step 4: Reverse the suffix (everything after pivot)
digits[pivot + 1..].reverse();
// Convert digits back to i64
digits.iter().collect::<String>().parse::<i64>().unwrap_or(-1)
}
fn main() {
println!("Result: {}", next_greater_number(534965)); // 535469
println!("-----------------------------");
println!("Result: {}", next_greater_number(111)); // -1 (all digits identical)
println!("-----------------------------");
println!("Result: {}", next_greater_number(7600)); // -1 (already the largest)
}
/*
run:
Result: 535469
-----------------------------
Result: -1
-----------------------------
Result: -1
*/
