{"id":639,"date":"2020-06-10T11:22:49","date_gmt":"2020-06-10T11:22:49","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=639"},"modified":"2022-03-23T06:53:08","modified_gmt":"2022-03-23T06:53:08","slug":"quality-factor","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/quality-factor\/","title":{"rendered":"Quality Factor"},"content":{"rendered":"

\"\"<\/p>\n

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

Basic Mathematics<\/p>\n<\/blockquote>\n

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

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

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

Given a magical container such that whenever :- <\/p>\n

    \n
  1. A Red Stone is added to the ith<\/sup> bag, the quality factor of i<\/code> to N<\/code> bags increases by 1<\/code>.<\/li>\n
  2. A Black Stone is added to the ith<\/sup> bag, the quality factor of i<\/code> to N<\/code> bags decreases by 1<\/code>.
    \nGiven an array of N<\/code> bags, task is to perform minimum no. of operations on the magical container and equalise both the containers.<\/li>\n<\/ol>\n<\/blockquote>\n

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

    For Example:<\/h4>\n
    Input : N = 5, A[] = [1, 2, 3, 4, 5]\n\nOutput : 5 \n\nExplanation : \n\nQuality factor of given container   [1, 2, 3, 4, 5]\nQuality factor of magical container [0, 0, 0, 0, 0]\n\nAdding a Red stone at index 0,\nQuality factor of given container   [1, 2, 3, 4, 5]\nQuality factor of magical container [1, 1, 1, 1, 1]\n\nAdding a Red stone at index 1,\nQuality factor of given container   [1, 2, 3, 4, 5]\nQuality factor of magical container [1, 2, 2, 2, 2]\n\nAdding a Red stone at index 2,\nQuality factor of given container   [1, 2, 3, 4, 5]\nQuality factor of magical container [1, 2, 3, 3, 3]\n\nAdding a Red stone at index 3,\nQuality factor of given container   [1, 2, 3, 4, 5]\nQuality factor of magical container [1, 2, 3, 4, 4]\n\nAdding a Red stone at index 4,\nQuality factor of given container   [1, 2, 3, 4, 5]\nQuality factor of magical container [1, 2, 3, 4, 5]\n\nBoth containers are equalised by performing 5 operations.<\/code><\/pre>\n
    OBSERVATION:<\/h3>\n
    \n
    Whenever a stone is added to a bag, it affects all the bags from i<\/code> to N<\/code> bags i.e. all bags including the current one and all to the right of it. While the left bags remain unchanged.    <\/p>\n
    Can you now think of something that can be used using this Hint before going to the solution?<\/em><\/strong><\/p>\n<\/blockquote>\n
    SOLVING APPROACH:<\/h3>\n
    \n
      \n
    1. The approach is to start from the left most side of the array and keep on equalising the elements in both the arrays. Because once we move ahead, our next actions will not disturb the left side of the array.    <\/li>\n
    2. Initialise current<\/code> and total<\/code> as 0<\/code> and start traversing the array from the left.  <\/li>\n
    3. for every element A[i]<\/code>, the absolute difference between the element and current<\/code> is the number of operations required to equalise ith<\/code> element of the Magical container<\/code> with A[i]<\/code>, keep adding the absolute difference to total<\/code>. Also update current<\/code> with A[i]<\/code>.    <\/li>\n
    4. Keep following the same procedure for equalising each and every element.<\/li>\n<\/ol>\n<\/blockquote>\n
      ILLUSTRATION:<\/h3>\n
      A[] = [1, 2, 3, 2]\nQ[] = [0, 0, 0, 0]\n\ncount = 0\ncurrent = 0\n\ni = 0\ncount = count + abs(A[i] - current) = 0 + abs(A[0] - 0) = 0 + 1 = 1\ncurrent = A[0] = 1\ni++ \n\ni = 1\ncount = count + abs(A[i] - current) = 1 + abs(A[1] - 1) = 1 + abs(2 - 1) = 2\ncurrent = A[1] = 2\ni++ \n\ni = 2\ncount = count + abs(A[i] - current) = 2 + abs(A[2] - 2) = 2 + abs(3 - 2) = 3\ncurrent = A[2] = 3\ni++\n\ni = 3\ncount = count + abs(A[i] - current) = 3 + abs(A[3] - 3) = 3 + abs(2 - 3) = 4\ncurrent = A[3] = 2\ni++ \n\nTotal operations to be performed are 4.<\/code><\/pre>\n
      SOLUTIONS:<\/h3>\n
      \t\t\t\t\t\t