{"id":1060,"date":"2020-06-10T11:58:17","date_gmt":"2020-06-10T11:58:17","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1060"},"modified":"2022-03-10T20:00:08","modified_gmt":"2022-03-10T20:00:08","slug":"magical-ropes","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/magical-ropes\/","title":{"rendered":"Magical Ropes"},"content":{"rendered":"

\"\"<\/p>\n

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

Binary Search<\/p>\n<\/blockquote>\n

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

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

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

Given an array H<\/code> of lengths of Magical<\/code> Ropes and array R<\/code> of the rate by which rope increases daily, print the minimum number of days required to collect ropes that sum up to length X<\/code> <\/p>\n<\/blockquote>\n

Restrictions<\/strong>:<\/p>\n

\n
    \n
  1. \n

    You cannot cut the rope, you have to take complete rope for collecting it. <\/p>\n<\/li>\n

  2. \n

    You cannot take a rope with length<\/code> less than K<\/code>.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n

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

    For Example:<\/h4>\n
    Input : N = 4, X = 100, K = 45\n        Heights[] = [2, 5, 2, 6]\n           Rate[] = [10, 13, 15, 12]\nOutput : 4\n\nExplanation :\n\nDay 0 = [2, 5, 2, 6]\n\nDay 1 = [2 + 10, 5 + 13, 2 + 15, 6 + 12]         = [12, 18, 17, 18]\n\nDay 2 = [12 + 10, 18 + 13, 17 + 15, 18 + 12]     = [22, 31, 32, 30]\n\nDay 3 = [22 + 10, 31 + 13, 32 + 15, 30 + 12]     = [32, 44, 47, 42]\n\nDay 4 = [32 + 10, 44 + 13, 47 + 15, 42 + 12]     = [42, 57, 62, 54]\n\nAns : Day 4 as (57, 62, 54 are all greater than 45 and sum up to value that is greater than equal to 100)<\/code><\/pre>\n
    Can we use Binary Search<\/code> here ?<\/em><\/strong>  <\/p>\n
    \n
    We need to find the minimum days required to collect ropes that sum up to length X<\/code>. The required day can be any day between 0<\/code> to 1018<\/sup> We can use Binary Search<\/code> for finding the right day efficiently in Logarithmic Time Complexity<\/code>.<\/p>\n<\/blockquote>\n
    SOLVING APPROACH:<\/h3>\n
    \n
    NOTE<\/strong>: As the length of rope is increasing by a given pace so we can calculate its length at any particular day by :-  <\/p>\n
    Lenght at ith day = ith day * Rate of Growth + Initial length<\/code><\/p>\n
      \n
    1. \n
      The idea is to perform a Binary Search<\/code> such that whenever we find a day<\/code> in which ropes length sum up to X<\/code>, we will save it and search for a even lower value (as Minimum days<\/code> are needed).  <\/p>\n<\/li>\n
    2. \n
      initialize low<\/code> as 0<\/code> and high<\/code> as 10^{18}<\/code>, by this we understand that minimum days can be as low as value of low<\/code> and as high as value of high<\/code>.<\/p>\n<\/li>\n
    3. \n
      Calculate  mid = (low + high)\/2<\/code>, say mid<\/code> is our desired day.<\/p>\n<\/li>\n
    4. \n
      Now, Linearly traverse and check for all ropes if their length at mid<\/code> day is greater than or equal to K<\/code>, if Yes add its value to a variable Sum<\/code>.<\/p>\n<\/li>\n
    5. \n
      After traversal if Sum<\/code> becomes greater or equal to X<\/code>, simply save it, and check for a even lower value in the left half i.e. (low - (mid - 1))<\/code>.<\/p>\n<\/li>\n
    6. \n
      Else, search in the right half i.e. ((mid + 1) - high)<\/code>.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
      SOLUTIONS:<\/h3>\n
      \t\t\t\t\t\t