JNEXT - Just Next !!!

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.


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.


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.


1 5 4 8 3
1 4 7 4 5 8 4 1 2 6


hide comments
vivek_01: 2019-03-20 19:52:22

Quite easy ,
NlogN in worst case would work fine
used multiset and upper_bounds.....
matter of seconds

aditya_305: 2019-01-30 14:02:19

Done using next_permution function in c++ STL.. LOL

dex_coder007: 2018-12-06 12:44:59

How to do it with stacks?

ilovemetoo: 2018-11-17 09:24:47

AC in one go!! Yay!

debsourav33: 2018-10-31 14:09:43

Alright! Done using sorting! Previous O(NlogN) solution using multiset gave TLE but stl sort works! Guess STL sort has slightly better than NlogN runtime..

debsourav33: 2018-10-30 15:10:43

10^6 is too big dataset for my beautiful nlogn solution using multiset and binarysearch.. :(

thesyncoder: 2018-10-24 11:15:22

Little hard,
try doing it for test cases like - 1 6 8 7 5
and consider the failing test cases(-1) too like 741 or 4

k_chaitanya98: 2018-10-09 17:40:09

I am running this code in another IDE and getting this correct in JAVA but getting Wrong Answer here .Can Somebody tell me corner cases that I need to cover

saketag007: 2018-09-30 17:39:57

Easy AC in one go. Check for this test case
1 0 8 7 6

shubham_04_04: 2018-09-21 20:26:21

Took 20 attempt to get it correct :( for 25th

Last edit: 2018-09-25 17:41:47

Added by:! include(L.ppt)
Time limit:1.297s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:MNNIT OPC 31-08-2012