{"id":1299,"date":"2020-07-01T09:23:46","date_gmt":"2020-07-01T09:23:46","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1299"},"modified":"2022-06-17T07:05:16","modified_gmt":"2022-06-17T07:05:16","slug":"copying-hero","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/copying-hero\/","title":{"rendered":"Copying Hero"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Sorting<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

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

We need to find the total number of steps need to make the current array of size N<\/code> same as an array containing 1 to N<\/code> numbers as elements. Each decrement or increment is counted as a step.<\/p>\n<\/blockquote>\n

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

Test Case:<\/h4>\n
Input:\n1\n5\n8 4 2 1 9\n\nOutput:\n9\n\nExplanation:\nAs our target array is [1,2,3,4,5], we already have 1, 2, and 4 in our array. We have 8 and 9 in place of 3 and 5, so if convert 8 to 3, and 9 to 5, we can achieve target array. Hence minimum increments\/decrements required will be (8-3)+(9-5)<\/code> ways i.e. 9 ways.<\/code><\/pre>\n
Solving Approach :<\/h3>\n
Observation:<\/strong> We can see that size of array goes from 1 to 106<\/sup>, in worse conditions let the size of the array be 106<\/sup> if we sort this array using any of sorting techniques i.e. Bubble Sort, Insertion Sort, Selection sort<\/em>. They all take O(n2<\/sup>) in the worst cases, which results in 1012<\/sup> iterations when the size of the array is 106<\/sup>. So we, can’t choose the above three sorting algorithms. We use Merge Sort<\/em><\/strong> to sort array as it sorts array in linearithmic time complexity<\/em><\/strong> (nlog(n)<\/code>).<\/p>\n
\n
    \n
  • By sorting the given array in non-decreasing order, it will make sure that the difference between element at current index and Hero array’s (Target array) element is minimum.<\/li>\n
  • Thus we can take the absolute difference between both elements, an increment or decrement, both will be taken as a step.<\/li>\n
  • Sum of all absolute differences is our final answer.<\/li>\n<\/ul>\n<\/blockquote>\n
    Example<\/h3>\n
    \n
    Let the arrays be,<\/p>\n
    \"\"<\/p>\n
    Now, we iterate on both arrays, and save absolute difference ob elements at same indexes in a variable sum<\/code> initially set to 0<\/code>.<\/p>\n
    \"\"<\/p>\n<\/blockquote>\n
    Solutions<\/h3>\n
    \t\t\t\t\t\t