sasse's blog

By sasse, history, 3 years ago, In English

Recently I was asked this question in an online interview. I am still unable to figure out how to solve this. The question is below.

You are given a string A of length N which consists of digits from 0 to 9 and two integer B and C. These are two operation which you can do on a string.

  1. Rotate
  2. Add

You can use Rotate operation to rotate a string clockwise by B positions. For example if B=1, string "**581**" will become "**158**". Also you can use Add operation to add number C to all odd indexes of string (0 based indexing). For example C=3, then string "**781**" will become "**711**". Digits post 9 are cycled back to zero.

You can use any of the two operation any number of times in any order to return the lexicographically smallest string.

For example 
A="31"
B=1
C=4
Results: "11"

Please help me with question. What approach to follow, or what algorithms to read upon. Thank you.

Efforts:

Case 1: C is even and N is even I thought of if C is even and N is even, then rotating it will not change the odd index number(odd indices number will remain odd indices so I go on to find the digit at some odd position which can yield me lowest digit after adding B, and then I will go on to add B to all the number. So my answer will be either original number A or changed number

Case 2: C is even and N is odd In this odd indices number can come on even indices too, so I find the number number that yields me smallest digit after adding B. and finally go on rotate it till I get that digit at 0th index, which will give me smallest number.

Case 3: C is odd and N is even This case is similar to case 2

Case 4: C is odd and N is odd This case is similar to case 1

Following this approach I am getting wrong answer. Can you point out me mistake and point in right direction.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone solve this?