Sponsored
Sponsored
This approach uses the concept of finding the next permutation of the digits of the number. We traverse the digits from right to left to find the first digit that is smaller than the digit next to it. Once found, we swap it with the smallest larger digit on its right and then reverse the sequence following the swapped digit.
Time Complexity: O(n log n) (due to sorting in worst case)
Space Complexity: O(1) (in-place swap and conversion)
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int compare(const void* a, const void* b) {
6 return (*(char*)a - *(char*)b);
7}
8
9int nextGreaterElement(int n) {
10 char digits[11];
11 sprintf(digits, "%d", n);
12 int len = strlen(digits);
13 int i, j;
14
15 for (i = len - 2; i >= 0; i--) {
16 if (digits[i] < digits[i + 1]) {
17 break;
18 }
19 }
20
21 if (i < 0) return -1;
22
23 for (j = len - 1; j > i; j--) {
24 if (digits[j] > digits[i]) {
25 break;
26 }
27 }
28
29 char temp = digits[i];
30 digits[i] = digits[j];
31 digits[j] = temp;
32
33 qsort(digits + i + 1, len - i - 1, sizeof(char), compare);
34
35 long long newNumber = atoll(digits);
36 return (newNumber > INT_MAX) ? -1 : (int)newNumber;
37}
38
39int main() {
40 int n = 12;
41 printf("%d\n", nextGreaterElement(n));
42 return 0;
43}The solution involves converting the integer to a string and manipulating the characters to find the next permutation. We ensure to swap the digits right before reversing the tail end. We also handle possible overflow scenarios by checking if the result exceeds the 32-bit limit.
This approach entails understanding mathematical permutation generation principles. First, identify the point where the digits stop increasing when moving left-to-right, then swap it. Finally, regenerate that segment to form the smallest sequential increase.
Time Complexity: O(n^2) (as it checks for minimum swap position for small digits segment)
Space Complexity: O(n) (array storage)
1#include <iostream>
#include <vector>
#include <algorithm>
int nextGreaterElement(int n) {
std::string digits = std::to_string(n);
int i = digits.length() - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) i--;
if (i < 0) return -1;
int j = i + 1;
while (j + 1 < digits.length() && digits[j + 1] > digits[i]) j++;
std::swap(digits[i], digits[j]);
std::sort(digits.begin() + i + 1, digits.end());
long long result = std::stoll(digits);
return (result > INT_MAX) ? -1 : result;
}
int main() {
int n = 12;
std::cout << nextGreaterElement(n) << std::endl;
return 0;
}This solution considers creating permutations by sorting sub-sequences post-swap for incremental growth. It checks near-linear progression of larger values.