vaps2012000's blog

next number
By vaps2012000, history, 4 years ago, In English

how to find the next number which has all different digits and greater than the given number N? Like if N=2000 then the answer is 2013. how to approach this problem. where 1<=N<=10^16

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
4 years ago, # |
  Vote: I like it +42 Vote: I do not like it

The answer will not exits if it has more than 10 digits. for less than or equal to 10 digits you can form all the permutations.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you code in Python, you could use a dictionary that keeps adding the value TRUE for every digit of the number in consideration. After all the digits of the number have been traversed AND if a digit is found to already have a value TRUE in dictionary, clear the dictionary and move on to the next number. When a number with all digits distinct is found, break out of the loop.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that's working upto 10^8 ,but my need is upto 10^16.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      But how can it be upto 10^16 ? Digits will starting repeating in every number after 9876543210. :/

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you please post a link to this problem? Thanks!

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The question link u posted doesnt have such big limits on n..

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Here's my greedy approach sorry abit messy that I believe will work for any number. The idea is:

  • ans cannot exceed 9876543210

  • start from left to right and when you find the digit that occurred before increase it, if it's 9 in increasing it will genereate a carry which which we have to add toward left.

→ Reply