using System;
public static class NextGreaterNumberUtil
{
// 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
public static long NextGreaterNumber(long n) {
// Convert number to array of characters (digits)
char[] digits = n.ToString().ToCharArray();
int length = digits.Length;
// Step 1: Find pivot (first digit from right that is smaller than the next)
int 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
int j = length - 1;
while (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)
int left = i + 1;
int right = length - 1;
while (left < right) {
(digits[left], digits[right]) = (digits[right], digits[left]);
left++;
right--;
}
// Convert char array back to long
long result = 0;
foreach (char c in digits) {
result = result * 10 + (c - '0');
}
return result;
}
}
class Program
{
static void Main()
{
Console.WriteLine("Result: " + NextGreaterNumberUtil.NextGreaterNumber(534965)); // 535469
Console.WriteLine("-----------------------------");
Console.WriteLine("Result: " + NextGreaterNumberUtil.NextGreaterNumber(111)); // -1 (all digits identical)
Console.WriteLine("-----------------------------");
Console.WriteLine("Result: " + NextGreaterNumberUtil.NextGreaterNumber(7600)); // -1 (already the largest)
}
}
/*
run:
Result: 535469
-----------------------------
Result: -1
-----------------------------
Result: -1
*/
