Untitled
unknown
plain_text
3 months ago
3.7 kB
5
Indexable
### Intuition and Thought Process This problem is a variation of **Next Permutation**, where we need to find the next lexicographically greater number using the same digits. 1. **Identify the First Decreasing Digit from the Right** - Start from the rightmost digit and move left until you find the first digit that is **smaller than** the digit immediately after it. This is the **pivot**. - If no such pivot is found, it means the number is the largest permutation (e.g., `21`), so return `-1`. 2. **Find the Smallest Digit Greater than Pivot** - Scan the digits to the right of the pivot and find the **smallest digit that is larger than the pivot**. - Swap these two digits to make the number larger. 3. **Sort (Reverse) the Remaining Digits** - To ensure we get the **smallest possible** number greater than `n`, sort (or reverse) the digits **after** the pivot position. 4. **Check for 32-bit Integer Overflow** - Convert the final result back to an integer. - If it exceeds `Integer.MAX_VALUE` (i.e., `2^31 - 1`), return `-1`. ### Java Implementation ```java import java.util.*; public class NextGreaterElement { public int nextGreaterElement(int n) { char[] digits = Integer.toString(n).toCharArray(); int len = digits.length; // Step 1: Find the first decreasing digit from the right int i = len - 2; while (i >= 0 && digits[i] >= digits[i + 1]) { i--; } // If no such index is found, return -1 if (i == -1) return -1; // Step 2: Find the smallest digit on the right that is larger than digits[i] int j = len - 1; while (digits[j] <= digits[i]) { j--; } // Step 3: Swap the two numbers swap(digits, i, j); // Step 4: Reverse the remaining digits to get the smallest permutation reverse(digits, i + 1, len - 1); // Convert back to integer and check for overflow long result = Long.parseLong(new String(digits)); return (result > Integer.MAX_VALUE) ? -1 : (int) result; } private void swap(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private void reverse(char[] arr, int start, int end) { while (start < end) { swap(arr, start++, end--); } } public static void main(String[] args) { NextGreaterElement obj = new NextGreaterElement(); System.out.println(obj.nextGreaterElement(12)); // Output: 21 System.out.println(obj.nextGreaterElement(21)); // Output: -1 System.out.println(obj.nextGreaterElement(54321)); // Output: -1 System.out.println(obj.nextGreaterElement(12443322)); // Output: 13222344 } } ``` ### Complexity Analysis - **Finding the pivot:** O(n) - **Finding the correct swap position:** O(n) - **Swapping:** O(1) - **Reversing the remaining portion:** O(n) - **Converting to integer:** O(n) **Total Complexity:** O(n), where `n` is the number of digits in the number. ### Edge Cases Considered 1. **Already Largest Permutation:** - If `n = 21`, `54321`, etc., return `-1`. 2. **Single Digit Numbers:** - If `n = 7`, return `-1` (since no greater number is possible). 3. **Numbers with Repeating Digits:** - If `n = 12443322`, the output should be `13222344`. 4. **Largest 32-bit Integer Handling:** - If the result exceeds `2^31 - 1`, return `-1`. This method ensures that we find the next greater number efficiently and correctly.
Editor is loading...
Leave a Comment