CODEWITHSUNDEEP
algorithmstl-algorithm
1shubhamjoshi1
1shubhamjoshi1

Reputation: 556

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.

Upvotes: 3

Views: 3515

Answers (4)

Rahul Tewari
Rahul Tewari

Reputation: 1

def getNextEven(self,x):
    s,p,flag,r = [],0,0,int(x)
    for i in x:
        p +=int(i)
        if int(i)%2==0:
            flag=1
        s.append(i)
    
    if flag==0:
        return -1
     
    n,x = len(s),int(x)
    
    while r%2!=0 or r<=x:
        l,k = -1,-1
        for i in range(n-2,-1,-1):
            if s[i]<s[i+1]:
                k = i
                break
        if k==-1:
            return -1
        
        for i in range(k+1,n):
            if s[k]<s[i]:
                l = i
               
        
        s[k],s[l] = s[l],s[k]
        s = s[:k+1]+s[k+1:][::-1]
        r = int(''.join(s))
        
    return r

Upvotes: 0

asn
asn

Reputation: 2607

  1. Find the next greater number for a given number. For eg - for 1234, the next greater number is 1243 and for 534976 the next greater is 536479. The algorithm can be found here. If the last digit is even then you've found the next greater even number.
  2. Otherwise, repeat the above step until we find the even number.ie-find the next greater even number than this with the now the new input number as the one that we output in the previous step (even if we didn't find the desired output(greater even number))

For eg - Input number - 21856521, running the first steps yields - 21861255(odd) so we again run step 1 on 21861255 which yields 21861525(again odd), running again yields 21861552

PS: C++ code:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int main(){
    string s;cin>>s;
    int n = s.length();
    while(true){
        int idx = -1;
        for(int i=n-2;i>=0;--i){
            if(s[i]<s[i+1]){
                idx = i;
                break;
            }
        }
        if(idx==-1){
            cout<<-1<<endl;
            break;
        }
        int swapidx = -1;
        for(int i=n-1;i>=idx+1;--i){
            if(s[i]>s[idx]){
                swapidx = i;
                break;
            }
        }
        swap(s[idx],s[swapidx]);

        //swapidx will never remain -1 bcz. we will surely find an element greater than s[idx](the right next element to idx is greater than s[idx])


        sort(s.begin()+idx+1,s.end());

        if((s[n-1]-'0')%2==0){
            cout<<s<<endl;
            break;
        }
    }
    return 0;
}

Upvotes: 0

Gijs Den Hollander
Gijs Den Hollander

Reputation: 723

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

Upvotes: 2

גלעד ברקן
גלעד ברקן

Reputation: 23945

Find the rightmost digit, i, that has a higher digit, j, to its right, where j is not the highest even digit to its right, e. Pick the smallest such j, switch i and j, place e as the rightmost digit, and sort (ascending) the digits to the right of where i was (excluding e).

Upvotes: 0

Related Questions