Question

How to find the smallest number greater than a given number, using the same digits in C++

Answer 1

#include <iostream>
#include <vector>
#include <algorithm>

// Time Complexity: O(n)
// One pass from right to left
// One pass from right to left again
// One reverse of a suffix
// No heavy memory usage

long long nextGreaterNumber(long long n) {
    // Convert number to vector of digits (as chars)
    std::vector<char> digits;
    for (char c : std::to_string(n)) {
        digits.push_back(c);
    }

    int length = digits.size();

    // Step 1: Find pivot
    int i;
    for (i = length - 2; i >= 0; --i) {
        if (digits[i] < digits[i + 1]) {
            break;
        }
    }

    if (i < 0) {
        return -1;
    }

    // Debug print (pivot digit)
    std::cout << digits[i] << std::endl;

    // Step 2: Find smallest digit to the right that is larger
    int j;
    for (j = length - 1; j > i; --j) {
        if (digits[j] > digits[i]) {
            break;
        }
    }

    // Debug print (digit to swap with)
    std::cout << digits[j] << std::endl;

    // Step 3: Swap
    std::swap(digits[i], digits[j]);

    // Debug print (after swap)
    std::cout << "[";
    for (int k = 0; k < length; k++) {
        std::cout << "'" << digits[k] << "'";
        if (k < length - 1) std::cout << ", ";
    }
    std::cout << "]" << std::endl;

    // Step 4: Reverse suffix
    reverse(digits.begin() + i + 1, digits.end());

    // Debug print (suffix after reverse)
    std::cout << "[";
    for (int k = i + 1; k < length; k++) {
        std::cout << "'" << digits[k] << "'";
        if (k < length - 1) std::cout << ", ";
    }
    std::cout << "]" << std::endl;

    // Convert back to integer
    long long result = 0;
    for (char c : digits) {
        result = result * 10 + (c - '0');
    }

    return result;
}

int main() {
    long long r1 = nextGreaterNumber(534965);
    std::cout << "Result: " << r1 << std::endl;
    std::cout << "---------------------------------" << std::endl;
    std::cout << "Result: " << nextGreaterNumber(111) << std::endl;
    std::cout << "---------------------------------" << std::endl;
    std::cout << "Result: " << nextGreaterNumber(7600) << std::endl;
}



/*
run:

4
5
['5', '3', '5', '9', '6', '4']
['4', '6', '9']
Result: 535469
---------------------------------
Result: -1
---------------------------------
Result: -1

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <vector>
#include <algorithm>

using std::cout;
using std::endl;

// Time Complexity: O(n)
// One pass from right to left
// One pass from right to left again
// One reverse of a suffix
// No heavy memory usage

long long nextGreaterNumber(long long n) {
    // Convert number to vector of digits
    std::vector<char> digits;
    for (char c : std::to_string(n)) {
        digits.push_back(c);
    }

    int length = digits.size();

    // Step 1: Find pivot (first digit from right that is smaller than next)
    int i;
    for (i = length - 2; i >= 0; --i) {
        if (digits[i] < digits[i + 1]) {
            break;
        }
    }

    // If no pivot found → digits are in descending order → no larger number
    if (i < 0) {
        return -1;
    }

    // Step 2: Find smallest digit to the right of pivot that is larger than pivot
    int j;
    for (j = length - 1; j > i; --j) {
        if (digits[j] > digits[i]) {
            break;
        }
    }

    // Step 3: Swap pivot with that digit
    std::swap(digits[i], digits[j]);

    // Step 4: Reverse the suffix to get the smallest possible number
    reverse(digits.begin() + i + 1, digits.end());

    // Convert back to integer
    long long result = 0;
    for (char c : digits) {
        result = result * 10 + (c - '0');
    }

    return result;
}

int main() {
    cout << "Result: " << nextGreaterNumber(534965) << endl;
    cout << "-----------------------------" << endl;
    cout << "Result: " << nextGreaterNumber(111) << endl; // -1 (all digits identical)
    cout << "-----------------------------" << endl;
    cout << "Result: " << nextGreaterNumber(7600) << endl; // -1 (already the largest)
}



/*
run:

Result: 535469
-----------------------------
Result: -1
-----------------------------
Result: -1

*/

 

70+ SQL courses for beginners and professionals