Find Next Greater Number by Rearranging Same Digits

let's take Number: 14650

Step 1: loop from the left end towards the start and find the point where the current element arr[i] is greater than its right arr[i-1].

i= 2, arr[2] = 6 is greater than arr[i-1] = 4

 

Step 2: loop from i to end and find the min element which is greater than arr[i-1] and less than arr[i] ie a[i-1] < min < arr[i]

i = 3, arr[3] = 5 is greater then arr[i-1] = 4 and less then arr[i] = 6

 

Step 3: Swap arr[i-1] and min

swap 4 and 5 so the new number will be 15640

 

Step 4: Sort all remaining elements after min in ascending order.

sort {6,4,0} in ascending order, hence {0,4,6}

Next Largest Number: 15046

package org.wesome.dsalgo;

import java.util.Arrays;

public class NextGreaterNumber {
    public static int[] nextGreaterNumber(int[] arr) {
        int indx, size = arr.length;
        /*  loop from left end towards start and find the point where current element arr[i] is greater than its right arr[i-1] */
        for (indx = size - 1; indx > 0; indx--) {
            if (arr[indx] > arr[indx - 1]) {
                break;
            }
        }
        /*  if indx reached till start, means number is already in the greatest combination */
        if (indx == 0) {
            System.out.println(Arrays.toString(arr) + " is already in greatest combination");
        } else {
            /*  loop from i to end and find the min element which is greater than arr[i-1] and less than arr[i] ie a[i-1] < min < arr[i]    */
            int min = indx;
            for (int j = indx + 1; j < size; j++) {
                if (arr[j] > arr[indx - 1] && arr[j] < arr[min]) {
                    min = j;
                }
            }
            /*  Swap arr[indx-1] and min   */
            int temp = arr[indx - 1];
            arr[indx - 1] = arr[min];
            arr[min] = temp;
            /*  Sort all remaining elements after min in ascending order    */
            Arrays.sort(arr, indx, size);
            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }
}

package org.wesome.dsalgo;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import static org.wesome.dsalgo.NextGreaterNumber.nextGreaterNumber;

public class NextGreaterNumberTest {
    @Test
    void nextGreaterNumberTest() {
        int arr[] = {1, 4, 6, 5, 0};
        Assertions.assertArrayEquals(new int[]{1, 5, 0, 4, 6}, nextGreaterNumber(arr));
    }
}

plugins {
    id 'java'
    id "io.freefair.lombok" version "6.2.0"
}

group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8

configurations {
    compileOnly {
        extendsFrom annotationProcessor
    }
}

repositories {
    mavenCentral()
}

dependencies {
    testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}

test {
    useJUnitPlatform()
}