Given the number N, we find the smallest even number E such that E> N

Question

Given the number N, we find the smallest even number E such that E> N and the digits in N and E are the same.

   Print NONE otherwise.
    Sample:
Case1
    Input
    N = 34722641 
    Output
    E = 34724126
Case2
    Input
    N = 8234961
    Output
    E = 8236194 (instead of 8236149)

My second case passed the first case, I get the wrong conclusion

public static int nextDigit(int number) {
String num = String.valueOf(number);
int stop = 0;
char[] orig_chars = null;
char[] part1 = null;
char[] part2 = null;
orig_chars = num.toCharArray();

for (int i = orig_chars.length - 1; i > 0; i--) {
    String previous = orig_chars[i - 1] + "";
    String next = orig_chars[i] + "";
    if (Integer.parseInt(previous) < Integer.parseInt(next))
{
    if (Integer.parseInt(previous) % 2 == 0) {

        String partString1 = "";
        String partString2 = "";
        for (int j = 0; j <= i - 1; j++) {
            partString1 = partString1.concat(orig_chars[j] + "");
        }
        part1 = partString1.toCharArray();
        for (int k = i; k < orig_chars.length; k++) {
            partString2 = partString2.concat(orig_chars[k] + "");
        }
        part2 = partString2.toCharArray();
        Arrays.sort(part2);
        for (int l = 0; l < part2.length; l++) {
            char temp = '0';
            if (part2[l] > part1[i - 1]) {
                temp = part1[i - 1];
                part1[i - 1] = part2[l];
                part2[l] = temp;
                break;
            }
        }
        for (int m = 0; m < part2.length; m++) {
            char replace = '0';
            if (part2[m] % 2 == 0) {
                replace = part2[m];
                for (int n = m; n < part2.length - 1; n++) {
                    part2[n] = part2[n + 1];
                }
                part2[part2.length - 1] = replace;
                break;
            }
        }

        System.out.print(part1);
        System.out.println(part2);
        System.exit(0);
        }
    }
}
     System.out.println("NONE");

  return 0;
    }

Answer 1

The first idea was to generate the next permutation until one was found. This works well for small entrances or when there is even a permutation nearby, but bad for large entrances, such as 2135791357913579, where many permutations must occur “to the right” before a single even digit is put back in place.

גלעד ברקן , .

• , j < j, i- j- . , , N.
• , i.
• (, , ), . .
• . .

Clojure . . , .

(defn num->digits [n] (mapv #(Character/getNumericValue %) (str n)))

(defn digits->num [v] (when (seq v) (read-string (apply str v))))

(defn swap 
  "Swap elements at index i and j in vector v"
  [v i j]
  (assoc (assoc v i (v j)) j (v i)))

(defn find-max-where
  "Find index i in vector v such that (v i) is the largest satisfying pred"
  [pred v] 
  (first 
    (reduce-kv 
      (fn [[k m] i x] 
        (if (and m (> m x)) 
          [k m] 
          (if (pred x) [i x] [k m]))) 
      [nil nil] 
      v)))

(defn next-even-perm [v] 
  (->>
    (for [j (range (count v))
          i (range j) 
          :when (< (v i) (v j))
          :let [v (swap v i j)
                k (find-max-where even? (vec (subvec v (inc i))))]
          :when k
          :let [v (swap v (+ (inc i) k) (dec (count v)))]] 
      (concat (subvec v 0 (inc i)) 
              (sort (subvec v (inc i) (dec (count v)))) 
              [(peek v)])) 
    (map vec) sort first))

(defn next-even-num [n] (-> n num->digits next-even-perm digits->num))

:

 (next-even-num 34722641) 
 ;=> 34724126

 (next-even-num 8234961)
 ;=> 8236194

 (next-even-num 4321) 
 ;=> nil (no solution)

(time (next-even-num 2135791357913579))
; "Elapsed time: 1.598446 msecs"
;=> 3111335557779992

(time (next-even-num 13244351359135913))
; "Elapsed time: 1.713501 msecs"
;=> 13245111333355994

(time (next-even-num 249999977777555553333311111N))
; "Elapsed time: 1.874579 msecs"
;=> 251111133333555577777999994N

, , , , , , . , , .

(next-even-num 1358) 
;=> 1538

Answer 2

Haskell A. Webb :

import qualified Data.Map as M
import Data.Ord (comparing)
import Data.List (sort,maximumBy)
import Data.Maybe (fromJust)

digs :: Integral x => x -> [x]
digs 0 = []
digs x = digs (x `div` 10) ++ [x `mod` 10]

nextE n
  | e == -1   = "NONE"
  | otherwise = concatMap show $ take (ie' + 1) (M.elems s)
              ++ sort (drop (ie' + 1) (M.elems s')) ++ [r]
 where ds = M.fromList (zip [0..] (digs n))
       rightMost (-1) _  = [(-1,0),(-1,0)]
       rightMost ix   xs
         | even (x) && not (null $ filter (>x) xs) = [(x,ix),(y,iy)]
         | otherwise                               = rightMost (ix - 1) (x:xs)
        where x = fromJust (M.lookup ix ds)
              (y,iy) = minimum . filter ((>= x) . fst) 
                     $ zip xs [ix + 1..M.size ds - 1]
       [(e,ie),(l,il)] = rightMost (M.size ds - 1) []
       s = M.insert il e . M.insert ie l $ ds
       (ir,r) = maximumBy (comparing snd) . M.toList 
              . M.filter even . snd $ M.split ie s
       s' = M.delete ir s
       ie' = fromIntegral ie

main = print (map (\x -> (x,nextE x)) [34722641,8234961,13244351359135913,3579])

:

*Main> main
[(34722641,"34724126"),(8234961,"8236194")
,(13244351359135913,"13245111333355994"),(3579,"NONE")]
(0.02 secs, 563244 bytes)

Answer 3

, .

20 , , N 12 . ( 1 , , )

, , , , , :

• N, , N - 12345, - 23xxx. ( xxx).

• N, N 12345, 12xxx.

, , .

, :

public int cal(boolean[] selected, int[] num, int digit, boolean larger) {
    //Arrays selected will tell which digit in N has already selected, 
    //int digit will tell currently, which digit we are checking
    //boolean larger tells is the number already larger than N

    if (digit + 1 == selected.length) {//Last digit
        for (int i = 0; i < selected.length; i++) {
            if (!selected[i]) {
                if (num[i] % 2 != 0) {
                    return -1; // -1 means this is an invalid value
                } else {
                    if (larger) {
                        return num[i];
                    } else {
                        return -1;
                    }
                }
            }
        }
    }
    int result = -1;
    for (int i = 0; i < selected.length; i++) {
        if (!selected[i]) {
            if (larger) {
                selected[i] = true;
                int val = (int) (num[i] * Math.pow(10, digit) + cal(selected, num, digit + 1, larger));
                if (val != -1 && (result == -1 || result > val)) {
                    result = val;
                }
            } else if (num[i] >= num[digit]) {
                int val = (int) (num[i] * Math.pow(10, digit) + cal(selected, num, digit + 1, num[i] > num[digit]));
                if (val != -1 && (result == -1 || result > val)) {
                    result = val;
                }
            }
        }
    }
    return result;
}

, boolean [] selected ( ). , int [mask][larger] dp

, digit , , , .

, :

import java.util.Arrays;


/**
 *
 * @author Trung Pham
 */
public class Test {

    public static void main(String[] args) {
        Test test = new Test();

        System.out.println(test.largest(2135791357913579L));

    }
    long[][] dp;

    public long largest(long N) {
        String val = "" + N;

        int[] num = new int[val.length()];
        for (int i = 0; i < num.length; i++) {
            num[i] = val.charAt(i) - '0';
         //   System.out.println(num[i] + " " + i);
        }
        dp = new long[1 << num.length][2];
        for (long[] a : dp) {
            Arrays.fill(a, -2);
        }
        return cal(0, num, 0);

    }

    public long cal(int mask, int[] num, int larger) {
        //Arrays selected will tell which digit in N has already selected, 
        //int digit will tell currently, which digit we are checking
        //int larger tells is the number already larger than N, if it is 1, it is larger, 0 is not.
        int digit = 0;
        for (int i = 0; i < num.length; i++) {
            if (((1 << i) & mask) != 0) {
                digit++;
            }
        }
        if (dp[mask][larger] != -2) {
            return dp[mask][larger];
        }
        if (digit + 1 == num.length) {//Last digit
            //System.out.println(mask + "  " + digit);
            for (int i = 0; i < num.length; i++) {
                if (((1 << i) & mask) == 0) {
                    if (num[i] % 2 != 0) {
                        return -1; // -1 means this is an invalid value
                    } else {
                        if (larger == 1) {
                            //  System.out.println(num[i] + " " + i);
                            return num[i];
                        } else {
                            return -1;
                        }
                    }
                }
            }
            return -1;
        }
        long result = -1;
        int l = num.length;
        for (int i = 0; i < num.length; i++) {
            if (((1 << i) & mask) == 0) {
                if (larger == 1) {
                    //System.out.println(num[i]* Math.pow(10,l - digit) + " " + digit);
                    long val = (long) (cal(mask | (1 << i), num, larger));


                    if (val != -1) {
                        val += num[i] * Math.pow(10, l - digit - 1);
                        if (result == -1 || result > val) {
                            result = val;
                        }
                    }
                } else if (num[i] >= num[digit]) {
                    long val = (long) (cal(mask | (1 << i), num, num[i] > num[digit] ? 1 : 0));
                    if (val != -1) {
                        val += num[i] * Math.pow(10, l - digit - 1);
                        if (result == -1 || result > val) {
                            result = val;
                        }
                    }
                }
            }
        }

        return dp[mask][larger] = result;
    }
}

, , , 0 9 , 0.

Answer 4

, "NONE":

• (0, 2, 4, 6, 8) . x.
• , . , S.

E = S + x ( + )

• 1 , .
• E, , 2 <= N, .

5 , E, . e. N, , e N. e N, . 1 e N E. , E1.

e > N% 10, E1, , E1 >= N/10 E1 . e <= N% 10, E1 , E1 > N/10 E1 . , E1, E1 ( e) .

You can take it from here and solve this problem, since only careful coding is required here to solve the next part of the problem.