I am working on a code challenge now. My solution got "time exceed" even I have optimized it. I am seeking for help about more efficient solution or optimizing my solution a step more.
The description of the problem is : Write a function which takes a positive integer as a string and returns the minimum number of operations needed to transform the number to 1. The number is up to 309 digits long, so there won't too many character than you can express in that many digits. The transform process is limited to three operations: 1. Add 1 2. Subtract 1 3. Divide the number by 2 (only even number allow here)
My idea is to use DFS to traverse all possible solution with memorization to speed it up. But it does exceed the time limitation. The problem can not use dp because dp require a very large array to memorize. Below is my code:
private static int dfs(String num, int step,Map<String,Integer> memory){
if(num.equals("1")){
return step;
}
Integer size = memory.get(num);
if(size != null && size < step){
return Integer.MAX_VALUE;
}
memory.put(num, step);
int min = Integer.MAX_VALUE;
int lastDigit = num.charAt(num.length() - 1) - '0';
if(lastDigit % 2 == 0){
min = Math.min(min, dfs(divideBy2(num), step + 1, memory));
}else{
min = Math.min(min, dfs(divideBy2(num), step + 2, memory));
min = Math.min(min, dfs(divideBy2(plusOne(num)), step + 2, memory));
}
return min;
}
private static String plusOne(String num){
StringBuilder sb = new StringBuilder();
int carry = 1;
for(int i = num.length() - 1; i >=0; i--){
int d = (carry + num.charAt(i) - '0') % 10;
carry = (carry + num.charAt(i) - '0') / 10;
sb.insert(0, d);
}
if(carry == 1){
sb.insert(0, carry);
}
return sb.toString();
}
private static String divideBy2(String num){
StringBuilder sb = new StringBuilder();
int x = 0;
for(int i = 0; i < num.length(); i++){
int d = (x * 10 + num.charAt(i) - '0') / 2 ;
x = (num.charAt(i) - '0') % 2 ;
if( i > 0 || (i == 0 && d != 0))
sb.append(d);
}
return sb.toString();
}
Note: After test several cases: I got some sense but can not generalize the rule. If the current number is odd. we got two choices here: plus 1 or subtract 1. The number after the operation can be divided by 2 more times, the steps will be shorter.
Update: Hi, guys, I work all the night and find a solution to pass the test. The idea is divide the problem into 2 sub-problem: 1. if the number is even, just divide it by two. 2. if the number is odd, choose the way let the number has more tailing zeros in its bit representation. I will explain more about the odd situation: if the number is odd, the last two bit can be "01" or "11". When it is "01", decrease it by 1 , which let the last two bit become to "00". If it is "11", increase it by 1, which generate "00". By doing this, the next even number generated by the odd number can be divided more times, which is really fast in practice. Below is my code, if you have some questions about the implementation, feel free to send me a message:
public static int answer(String n) {
// Your code goes here.
int count = 0;
while(!n.equals("1")){
if((n.charAt(n.length() - 1) - '0') % 2 == 0){
n = divideBy2(n);
}else if(n.equals("3") || lastTwoBit(n)){
n = subtractOne(n);
}else{
n = plusOne(n);
}
count++;
}
return count;
}
private static boolean lastTwoBit(String num){
int n = -1;
if(num.length() == 1){
n = Integer.valueOf(num);
}else{
n = Integer.valueOf(num.substring(num.length() - 2, num.length()));
}
if(((n >>> 1) & 1) == 0){
return true;
}
return false;
}
private static String subtractOne(String num){
if(num.equals("1")){
return "0";
}
StringBuilder sb = new StringBuilder();
int carry = -1;
for(int i = num.length() - 1; i >= 0; i--){
int d = carry + num.charAt(i) - '0';
if(d < 0){
carry = -1;
sb.insert(0, '9');
}else if((d == 0 && i != 0) || d > 0){
carry = 0;
sb.insert(0, d );
}
}
return sb.toString();
}
private static String plusOne(String num){
StringBuilder sb = new StringBuilder();
int carry = 1;
int i = 0;
for(i = num.length() - 1; i >=0; i--){
if(carry == 0){
break;
}
int d = (carry + num.charAt(i) - '0') % 10;
carry = (carry + num.charAt(i) - '0') / 10;
sb.insert(0, d);
}
if(carry ==0){
sb.insert(0, num.substring(0, i + 1));
}
if(carry == 1){
sb.insert(0, carry);
}
return sb.toString();
}
private static String divideBy2(String num){
StringBuilder sb = new StringBuilder();
int x = 0;
for(int i = 0; i < num.length(); i++){
int d = (x * 10 + num.charAt(i) - '0') / 2 ;
x = (num.charAt(i) - '0') % 2 ;
if( i > 0 || (i == 0 && d != 0))
sb.append(d);
}
return sb.toString();
}
