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.
- Rotate
- 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.