Menu
Given a number N, find the smallest even number E such that E > N and digits in N and E are 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 first case i am getting wrong output
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;
}
843
First idea was to generate the next permutation until an even one is found. This works well for small inputs or when an even permutation is nearby, but badly for large inputs such as 2135791357913579 where many permutations have to happen "to the right" before the sole even digit is moved into place.
גלעד ברקן suggested a patch which with minor adjustment provides a superior algorithm.
The algorithm in Clojure could be written as follows. I tried to stick to a fairly imperative style. See if you can translate.
(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))
Provided examples:
(next-even-num 34722641)
;=> 34724126
(next-even-num 8234961)
;=> 8236194
(next-even-num 4321)
;=> nil (no solution)
Hard cases for previous algorithm
(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
Latest edit fixes problem where we were always wanting to swap with an even number moving right instead of just having any even number to the right whether or not it was involved in the swap. For example, the following failed in the previous edit, now fixed.
(next-even-num 1358)
;=> 1538
Many has suggested permutation, but for this problem, dynamic programming with bit-mask will be another solution.
For dynamic programming, the number of digit can be up to 20 digits, while with normal permutation, it can only be used if N has less than 12 digits. (With time constraint is 1 second , typically for competitive programming)
So the idea is, starting from the most significant digit to the least significant digit, at each step, we try to find the smallest value starting from this digit to the end, at each digit, we have two cases:
If the number being created is already larger than N for example N is 12345 and currently, we are 23xxx. (We need to find the smallest xxx in this case).
If the number is not yet larger than N , example N is 12345 and we have 12xxx.
Moreover, at the last digit, we need to determine if the created number is even or odd.
So, we have our simple recursive code:
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;
}
From this state, we notice that actually, the boolean [] selected can be replaced by a bit-mask value (Read about bitmask here Link) , So we can easily represent the state of this recursive by this array int [mask][larger] dp
Notice that the parameter digit is not necessary as we can easily determine the digit we are checking by counting the number of digit left to be selected.
Finally, we have our solution:
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;
}
}
Notice that this solution can still be improved if you notice that at each digit, we only selected value from 0 to 9 once, and the start digit cannot start with 0.
40
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With