{"id":1398,"date":"2020-06-11T03:12:55","date_gmt":"2020-06-11T03:12:55","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1398"},"modified":"2022-03-28T00:55:54","modified_gmt":"2022-03-28T00:55:54","slug":"block-move","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/block-move\/","title":{"rendered":"BLOCK MOVE"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Greedy algorithm.<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Easy.<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

You are given N blocks and the ith block is at position A[i]. Your task is to move every block to one single position. For that you can perform any of the two moves any number of times(possibly zero) on any block:<\/p>\n

    \n
  1. Move the ith block by 2 units to the left or to the right with a cost of 0.<\/li>\n
  2. Move the ith block by 1 unit to the left or to the right with a cost of 1. It is possible that there is more than one block at the same position initially.<\/li>\n<\/ol>\n<\/blockquote>\n

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

    For Example :<\/h4>\n
    2\n6\n1 3 3 6 4 8\n5\n9 2 1 7 8\n\n3\n2\n\nIn the first test case,\n1. Block at position \n1 will move to 3 at no cost.\n2. Block at position 4 will move to 3 with a cost of 1.\n3. Block at position 6 will move to 4 with no cost, and then move to 3 with a cost of 1.\n4. Block at position 8 will move to 6, then to 4 with no cost, and from 4 to 3 with a cost of 1.\nSo total cost = 3.<\/code><\/pre>\n
    OBSERVATION:<\/h3>\n
    \n
    Have you noticed that to move from an even position to another even position or to move from an odd position to another odd position incurs no cost?<\/p>\n<\/blockquote>\n
    SOLVING APPROACH:<\/h3>\n
    \n
    To get the minimum cost, choosing any odd position if the maximum number of given positions is odd or choosing any even position if the maximum number of given positions is even incurs the least cost because –<\/p>\n
    moving the block from odd position to another odd position or from even to another even takes 0 cost .<\/p>\n
    Amount is spend only when we move from even to odd or odd to even.<\/p>\n
    Count the number of odds i.e. the number of blocks at odd positions initially .
    \nAlso count the number of evens.
    \nThe greater of the two will the desired chosen final position!<\/p>\n<\/blockquote>\n
    SOLUTIONS:<\/h3>\n\t\t\t\t\t\t