Binary Number Game

Interview

Time limit1sMemory limit1024 MB

Summary

Given two binary strings, find the minimum number of single-bit flips (never the leading bit), increments, and decrements to turn the start number into the target.

Level: Medium6 of 10
Topics: BFS, Dynamic programming, Bit manipulation, Math
Solved: No attempts yet

Problem

The binary number game turns a given start binary number into a target binary number using a few operations.

The operations available in this game are as follows.

Flip one digit to its complement. The most significant digit cannot be flipped.
101₂ → 111₂
Add 1 to the current number.
11₂ → 100₂
Subtract 1 from the current number. Subtraction is impossible when the current number is 0.
110₂ → 101₂

Given a start binary number and a target binary number, print the minimum number of operations needed to turn the start binary number into the target binary number. The leading digit of every given binary number is always 1.

Input

The first line gives the start binary number of length L. The second line gives the target binary number of length K. (1 ≤ L, K ≤ 10)

Output

Print the minimum number of operations needed to turn the start binary number into the target binary number.

Examples2

Example 1
Input
```
110
1000
```
Expected output
```
2
```
Example 2
Input
```
101
111
```
Expected output
```
1
```