JNEXT - Just Next

Problem taken from https://www.spoj.com/problems/JNEXT/

Problem

DevG likes too much fun to do with numbers. Once his friend Arya came and gave him a challenge, he gave DevG an array of digits which is forming a number currently (will be called as given number). DevG was challanged to find the just next greater number which can be formed using digits of given number. Now DevG needs your help to find that just next greater number and win the challenge.

Input

The first line have t number of test cases (1 <= t <= 100). In next 2*t lines for each test case first there is number n (1 <= n <= 1000000) which denotes the number of digits in given number and next line contains n digits of given number separated by space.

Output

Print the just next greater number if possible else print -1 in one line for each test case.

Note : There will be no test case which contains zero in starting digits of any given number.

Example

Input:
2
5
1 5 4 8 3
10
1 4 7 4 5 8 4 1 2 6

Output:
15834
1474584162

Analysis

Notations used

Notation	Meaning
$array(x)$	Array representation of integer $x$
$a$	An integer
$A$	$array(a)$
$a_{next}$	The just next integer obtained after permuting digits of $a$
$A_{next}$	$array(a_{next})$
$P(a)$	Set of all integers obtained by any permutation of digits in $a$
$P_{greater}(a)$	$\{p: p \in P(a) \ and \ p > a\}$
$indices(I)$	Set of all indices of array $A$
$n$	Length of array $A$

Observations

About $a_{next}$

Looking at the problem statement, these inferences can be made about $a_{next}$.

$a_{next} \in P_{greater}(a)$

$p \in P_{greater}(a) \implies p \geq a_{next}$

About $P_{greater}(a)$

An integer $x$ is greater than another integer $y$ if some decimal place of $x$ has a greater value than that of $y$ and more significant decimal places of $x$ are either greater or equal to that of $y$. With that in mind, we can infer the following

$p \in P_{greater}(a) \ with \ P_g \ as \ array(p) \\ \implies \exists k \in indices(I): \quad P_{greater}[i] = A[i] \ \forall \ i < k \quad \land \quad P_{greater}[i] > A[i] \ for \ i=k$

Let this index $k$ corresponding to any $p \in P_{greater}(a)$ be called $decision\_point(p)$

Also, when the decision point moves to the right, the value of the integer will be redused.

$p, q \in P_{greater}(a) \quad \land \quad decision\_point(p) > decision\_point(q) \implies p < q$

Revisiting $a_{next}$

We saw that $a_{next}$ is the least integer in $P_{greater}(a)$. This give us some valuable deductions. Firstly, $decision\_point(a_{next})$ has to be greater or equal to that of any other $p \in P_{greater}(a)$. Moreover, digit at the decision point should be lowest for $a_{next}$ compared to that of other $p \in P_{greater}(x)$ with same decision point. More still, $A_{next}$ must be sorted in increasing order after the decision point.

$decision\_point(a_{next}) >= decision\_point(p) \quad \forall p \in P_{greater}(a)$

$Let \ p \in P_{greater}(x) \quad and \\ Let P_{g} \ be \ array(p) \quad and \\ Let \ decision\_point(p) \ as \ d \quad and \\ Let \ d = decision\_point(a_{next}) \\ \ \\ Then \\ P_{g}[d] >= A_{next}[d] \quad and \\ A_{next}[d,\dots,n] = sorted(A_{next}[d,\dots,n])$

Algorithm

FindNext(A, n)
    decision_point = rightmost index i in A such that A[i] < A[i+1]
    if not decision_point
        return "Cannot permute to give a greater integer"
    interchange_index = rightmost index i such that A[i] > A[decision_point]
    swap A[decision_point] with A[interchange_index]
    reverse A[decision_point+1,...,n] inplace
    return integer value of A

Implementation in C

This solution has been accepted by spoj.com

#include <stdio.h>
#include <stdlib.h>

void findNext(int * num, int length){
    int i;
    int possible = 0;
    int basement;
    int ground;
    int temp;
    for(i=length-1;i>0;i--){
        if(num[i] > num[i-1]){
            possible = 1;
            basement = i-1;
            break;
        }
    }
    if(!possible){
        printf("-1\n");
        return;
    }
    ground = basement + 1;
    for(i=ground+1;i<length;i++){
        if(num[i] > num[basement]){
            ground = i;
        } else {
            break;
        }
    }
    temp = num[basement];
    num[basement] = num[ground];
    num[ground] = temp;

    int breakpoint = basement + 1;
    for(i=0;i<breakpoint;i++){
        printf("%d", num[i]);
    }
    for(i=length-1;i>basement;i--){
        printf("%d", num[i]);
    }
    printf("\n");
    return;
}

void main() {
    int instances;
    scanf("%d", &instances);
    {
        int i;
        int length;
        int num[1000000];
        for(i=0;i<instances;i++){
            scanf("%d", &length);
            int j;
            for(j=0;j<length;j++){
                scanf("%d", &num[j]);
            }
            findNext(num, length);
        }
    }
}