Number of rotations

2.6

5 votes
Algorithms, String Manipulation
Problem

Bob and his friend James love to play with numbers. Therefore, they both write one number each (X and Y respectively) on stone. Bob wants to impress James by converting his number into special numbers
and Bob knows only three ways that can change his number without touching the stone whare the numbers are written and each way uses K amount of rotations.

The three ways are as follows:

  1. Right rotation
  2. Left rotation
  3. Reverse cloning

If you have a number X = 11 and Y=10.

The binary form of 11 = 1011,10=1010.
The right rotation of 11 = 13 (1011 -> 1101).
The left rotation of 11 =  7 (1011 -> 0111).
Reverse cloning means reverse any bit of the number X.You can perform this operation if and only if the Y has that bit set. You cannot do reverse cloning only on the second and fourth bits.

Print the minimum amount of rotations required to perform this task or print −1 if is is not possible.

Note: X and Y are huge numbers. Therefore, they are given in the binary form and the length of the numbers are the same.

Input format

  • The first line contains integer K
  • The next 2 lines contain X and Y in binary form

Output format

Print the minimum amount of rotations required to perform this task or print −1 if is is not possible.

Constraints

1|X|=|Y|20001K2000

 

 

Sample Input
20
1011
1010
Sample Output
60
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

X = 1011,Y=1010,k=20

at 1st do a right rotation at X then X became -> 1101 it uses 20 amount of rotations

then do reverse cloning at bit position 0 (from left) we can do this because Y has that bit set too then X became ->0101 it uses 20 amount of rotations

at last do a left rotate at X then X became -> 1010 (which is equal to Y ( 1010 ) ) it uses 20 amount of rotations

so total amount of rotations equal 20+20+20=60

 

 

Editor Image

?