[leetcode] broken calculator

problem

code

• with while

class Solution {
    public int brokenCalc(int X, int Y) {
		int cnt = 0;
        while (Y > X) 
        {
            cnt++
            if (Y % 2 == 0) Y /= 2;
            else Y += 1;
        }
        return cnt + X - Y;
    }
}

• with recursion

const brokenCalc = (X, Y) => {
  if (X >= Y) return X - Y;
  else {
    if (Y % 2 == 0) return 1 + brokenCalc(X, Y / 2);
    else return 1 + brokenCalc(X, Y + 1);
  }
}

Time: O(logY)
Space: O(1), only cnt;

explanation

why? backwards??
The key concept for this problem is how to reduce the number of subtract operations. It is hard to anticipate when to use the subtraction first before the multiplication cuz the multiply operation doubles the effect of the subtract. On the other hand, division operation reduces the effect of addition operation in half. The division reduces the number of cases to choose.

to binary => shift right(divide by 2) or +1
ex1)
5, 8: 101, 
  1000 
  1=> (1000 >> 1): 100 
    2=> +1: 101

ex2)
1, 100: 1, 
  1100100 
  1=> 110010 
  2=> 11001 
  3=> 11010 
  4=> 1101 
  5=> 1110 
  6=> 111 
  7=> 1000 
  8=> 100 
  9=> 10 
  10=> 1
just need to choose shift right or add opration to make first digit 0

on the other hands
1, 100: 1, 1100100
	=> 1 what to use? - or *? we need to think find the best way...
    => 11
    => 111
    => 1111
    => 11111
    => 111111
    => 1111111
    => 1111110
    => 1111101
    => 1111100
    => 1111010
    => ... lol
 every time I shift left, the number of cases to be chosen increases..