Search code examples
algorithmstl-algorithm

Next Greater Even Number

We have a number N and the problem is to find the smallest even number E such that E > N and digits in N and E are same. Digits in N could be huge.

For example

  1. 1 -> 34722641 answer would be 34724126
  2. 111 -> no even number is possible just greater then it.
  3. 1123 -> output would be 1132

I have done it with brute force by making all the permutations of the digits of the number. I was thinking if a better approach is there for it? A code would be better.

Thanks.

Solution

  • You can use the following strategy in finding the next permutation:

    Lets say your number = 12344875 To find the next permutations which is bigger, you start from the right and find the first number is smaller than the previous one. In this case: number = 12344875, this is 4.

    Now you start from the 4 moving right and find the smallest number there. Which is the 5 -> 875. Now swap those 2 numbers resulting in 12345874.

    After the swap sort the numbers after the 5 in ascending order. 12345874 --> 12345784. This strategy will always lead to next permutations wich is bigger, only this gives both even and uneven numbers.

    So for finding the next even permutations, you need to change this slightly. If in last step you have an even number, permutate that part till its an even number.

    Otherwise start again from the right. And find the first even number, which has a larger number to its right side. For example with the number = 123475531. Now swap with smallest number to its right which is greater than 4. Resulting in the following 123575431.

    From this put the even number 4 at the end and put the numbers between the swapped numbers in ascending order, 123575314 --> 123513574.

    For the case were you have the following number 136531. There is no even number with a greater number to the right. So you look at the next number, and see if to the right there is a number wich is greater (but not the first even number). Here it is for 136531 --> 136531 so swap those and put the even number at the back and finally put in ascending order. 136531 --> 156331 --> 153316 --> 151336.

    There is no solution when the number is in descending order(for example 97654).

    While making this explaination I realised that for an even number this gets more convoluted. Ill try to improve the answer later on.

    I hope this was useful. Cheers