{"id":813,"date":"2020-06-10T11:35:57","date_gmt":"2020-06-10T11:35:57","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=813"},"modified":"2022-03-25T11:43:16","modified_gmt":"2022-03-25T11:43:16","slug":"square-moves","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/square-moves\/","title":{"rendered":"Square Moves"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h4>\n
\n

Strings, Hash Table<\/p>\n<\/blockquote>\n

Difficulty Level<\/h4>\n
\n

Hard<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h4>\n
\n

Find the total number of children standing on each square after 10100<\/sup> rotations by every individual child. Each child moves according to 'R'<\/code> or 'L'<\/code> written on each square. Where R<\/code> stands for right and L<\/code> stands for left.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case<\/h4>\n
Input:\nRRLRL\n\nOutput:\n0 1 2 1 1\n\nExplanation:\nAfter each child had moved one place to their left or right as written on their square, their final count becomes\n0 2 1 1 1\nNow 2 children are standing on 2nd square and 1 square on 3rd, 4th and 5th square each. After repeating the same procedure for 10^100 steps, their final position becomes,\n0 1 2 1 1<\/code><\/pre>\n
Solving Approach :<\/h3>\n
Bruteforce Approach<\/strong> :<\/p>\n
\n
1) We can move each child by direction written on his square, after all, children have moved, we repeat this step for 10100<\/sup> times. After all, steps have completed, we print final counts.
\n2) By looking above approach we can see it would take infinite time even to process an array of smaller length. As compiler takes 1 second to process 10^{7}<\/code> procedures, so this program takes O(N\\times{10100<\/sup> }) time to solve this problem for an array of size N<\/code>.
\n3) We can’t solve this problem with this approach, so we look for a more efficient approach.<\/p>\n<\/blockquote>\n
Efficient Approach<\/strong> :<\/p>\n
\n
1) We know whenever the square direction is changed from Left<\/code> to Right<\/code> or Right<\/code> to Left<\/code>, i.e. when adjacent squares have a different direction, the child will rotate circularly for all next steps in these both squares. It will repeat its position after every 2 rotations in these two squares.
\n2) So if we can identify when the next Left<\/code> will be for the current square which directs to Right<\/code> or when was the previous Right<\/code> for the current square which directs Left<\/code>, We can solve this problem easily.
\n3) For a child standing on the square which directs to Right<\/code> <\/p>\n
    \n
  • Child will be standing on the first square stating Left<\/code> from its position if the distance between its initial position and next Left<\/code> square is even<\/code>.<\/li>\n
  • The position will be one less if the distance between its initial position and next Left<\/code> square is odd<\/code>.
    \n4) For a child standing on the square which directs to Left<\/code><\/li>\n
  • Child will be standing on last square stating Right<\/code> before it’s the position if the distance between its initial position and previous Right<\/code> square is even<\/code>.<\/li>\n
  • The position will be one closer if the distance between its initial position and previous Right<\/code> square is odd<\/code>.<\/li>\n<\/ul>\n<\/blockquote>\n
    Example<\/h3>\n
    \n
      \n
    • We can visualise above approach using an example. So let’s take the initial example we discussed in the test case section.<\/li>\n
    • Our squares have RRLRL<\/code> written. As every child moves according to direction written on the square, we can focus on a single child for understanding patterns.<\/li>\n
    • Let’s see movements for the child standing at index 0.<\/li>\n<\/ul>\n<\/blockquote>\n
      \"\"\"\"\"\"\"\"
      \n\"\"
      \n\"\"<\/p>\n
      \n
        \n
      • We can see the child has now gone into a loop where it is stuck at index 1<\/code> and 2<\/code> depending on the step number. After every 2 steps, it repeats its position. We observe the same for the child standing on left<\/code> square initially, for example, we can visualise same for the child standing at last square.  <\/li>\n<\/ul>\n<\/blockquote>\n
        \"\"
        \n\"\"
        \n\"\"
        \n\"\"<\/p>\n
        \n
          \n
        • We can observe children will rotate in the loop whenever the direction of adjacent squares will change.<\/li>\n
        • We can maintain an array which saves next Left<\/code> index and one for saving previous Right<\/code> index occurring for the current element.<\/li>\n
        • As mentioned in the efficient approach we can further calculate the position of the current child. For example, a child standing at index 0<\/code> will have next Left<\/code> at index 2<\/code>. So we will calculate the distance between both of them and check if it is even<\/code> or odd<\/code> and we’ll get final position for the child.<\/li>\n
        • We’ll increase the count in the hash table by 1, where the final position will be the index of the hash table.<\/li>\n
        • So final answer become 0 1 2 1 1<\/code>.<\/li>\n<\/ul>\n<\/blockquote>\n
          Solutions<\/h3>\n\t\t\t\t\t\t