Navigation

    ask avan logo
    • Register
    • Login
    • Search
    • Categories
    • Unsolved
    • Solved

    Finding minimum length of tape required.

    Algorithm
    2
    5
    46
    Loading More Posts
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes
    Reply
    • Reply as topic
    Log in to reply
    This topic has been deleted. Only users with topic management privileges can see it.
    • Padala Vamsi ujpNQUXGRi
      Padala Vamsi ujpNQUXGRi last edited by Padala Vamsi ujpNQUXGRi

      Can anyone just say how to solve this problem. I am not asking for code just a way to solve.

      Question:
      There is are m cabins numbered from 1 to m where n cabins are broken. You are provided with infinitely long tape which you are allowed to cut only k times. The task is to cover all the broken cabins with minimum length of tape used. You are provided with broken cabin positions, you are also allowed to cover non-broken cabins, and it is possible that some pieces of tape will overlap.

      Input Format
      First line contains three inputs n, m and k where n is number of cabins broken, m is total number of cabins, and k is number of tape pieces to be cut.
      Second line contains n integers b1, b2, b3 ...... bn represents positions of broken cabins in increasing order.

      Output Format
      print minimum total length of the pieces.

      Example:
      Input
      4 100 2
      20 30 75 80

      Output
      17

      Explanation:
      4 broken cabins, you need to cover broken cabins with 2 pieces of tape.
      cabins - Bold numbers are broken cabins
      1.......20........30....................75.......80........100
      ..........-----11-----___________ -----6-----_______
      length of tape used to cover cabin 20 and 30 is 11
      length of tape used to cover cabin 75 and 80 is 6
      so total length is 17

      If k=4 that means only 1 meter tape of 4 pieces are required to cover cabins 20, 30, 75, and 80 So the total length required is 4.

      I tried in many different ways by taking gaps between the broken cabins and by sorting them, but some cases are not getting solve. Please anyone just suggest algorithm to solve this problem. It is not urgent so you can take time to solve.

      Reply Quote 1
        1 Reply Last reply

      • avan
        avan last edited by

        Hey @Padala-Vamsi-ujpNQUXGRi

        Thank you for posting on my platform. This topic seems to somewhat be floating around the net.
        Here are some of the places this topic or similar ones are being mentioned:

        (Exact) https://www.codeproject.com/Questions/5294427/Finding-minimum-length-of-tape-required
        (Similar) https://leetcode.com/discuss/interview-question/972598/HashedIn-or-OA-or-Min-Tape-Length/792614

        I have come up with a recursive solution but I DON'T know if it's right. I wish we had more test cases so I could make sure.

        The idea is this:

        1. You loop through all the broken cabins and place the end of the first tape encompassing all broken cabins before it and then make a recursive call for the remaining cabins

        2. If the total length is less than the minimum length update the minimum length

        3. At the end return the minimum length

        Below is the (Java) code in case my vague explanation above is not enough. Keep in mind this has not been tested extensively and could definitely be wrong. I wish we had an official leetcode challenge where I could run my code...but oh well.

        SPACE INTENTIONALLY LEFT BLANK

        public static int minTape(int numBrokenCabins, int totalCabins, int numTapeCuts, int[] brokenCabins){
        	    int firstCabin = brokenCabins[0];
        	    int maxLength =  brokenCabins[brokenCabins.length-1] - firstCabin + 1;
        	    int minLength = maxLength;
        	    
        	    // Base cases
                if(numTapeCuts == 1){
                    return maxLength;
                }
                if(numTapeCuts == numBrokenCabins){
                    return numBrokenCabins;
                }
                
                for(int i = 0; i < brokenCabins.length-1; i++){
                    int currentCabin = brokenCabins[i];
                    int thisLength = currentCabin - firstCabin + 1;
                    int newNumBrokenCabins = numBrokenCabins - i - 1;
                    int newTotalCabins = totalCabins;
                    int newNumTapeCuts = numTapeCuts - 1;
                    int[] newBrokenCabins = Arrays.copyOfRange(brokenCabins, i+1, brokenCabins.length);
                    if(newNumBrokenCabins < newNumTapeCuts){
                        break;
                    }
                    int totalLength = thisLength + minTape(newNumBrokenCabins, newTotalCabins, newNumTapeCuts, newBrokenCabins);
                    minLength = totalLength < minLength ? totalLength : minLength;
                }
                
                return minLength;
        	}
        

        View and Run Code Online

        Please let me know if you find a mistake or if it fails for a specific case. I would love a chance to fix my code. Thank you.

        Reply Quote 0
          1 Reply Last reply

        • avan
          avan last edited by

          Hey @Padala-Vamsi-ujpNQUXGRi

          Thank you for posting on my platform. This topic seems to somewhat be floating around the net.
          Here are some of the places this topic or similar ones are being mentioned:

          (Exact) https://www.codeproject.com/Questions/5294427/Finding-minimum-length-of-tape-required
          (Similar) https://leetcode.com/discuss/interview-question/972598/HashedIn-or-OA-or-Min-Tape-Length/792614

          I have come up with a recursive solution but I DON'T know if it's right. I wish we had more test cases so I could make sure.

          The idea is this:

          1. You loop through all the broken cabins and place the end of the first tape encompassing all broken cabins before it and then make a recursive call for the remaining cabins

          2. If the total length is less than the minimum length update the minimum length

          3. At the end return the minimum length

          Below is the (Java) code in case my vague explanation above is not enough. Keep in mind this has not been tested extensively and could definitely be wrong. I wish we had an official leetcode challenge where I could run my code...but oh well.

          SPACE INTENTIONALLY LEFT BLANK

          public static int minTape(int numBrokenCabins, int totalCabins, int numTapeCuts, int[] brokenCabins){
          	    int firstCabin = brokenCabins[0];
          	    int maxLength =  brokenCabins[brokenCabins.length-1] - firstCabin + 1;
          	    int minLength = maxLength;
          	    
          	    // Base cases
                  if(numTapeCuts == 1){
                      return maxLength;
                  }
                  if(numTapeCuts == numBrokenCabins){
                      return numBrokenCabins;
                  }
                  
                  for(int i = 0; i < brokenCabins.length-1; i++){
                      int currentCabin = brokenCabins[i];
                      int thisLength = currentCabin - firstCabin + 1;
                      int newNumBrokenCabins = numBrokenCabins - i - 1;
                      int newTotalCabins = totalCabins;
                      int newNumTapeCuts = numTapeCuts - 1;
                      int[] newBrokenCabins = Arrays.copyOfRange(brokenCabins, i+1, brokenCabins.length);
                      if(newNumBrokenCabins < newNumTapeCuts){
                          break;
                      }
                      int totalLength = thisLength + minTape(newNumBrokenCabins, newTotalCabins, newNumTapeCuts, newBrokenCabins);
                      minLength = totalLength < minLength ? totalLength : minLength;
                  }
                  
                  return minLength;
          	}
          

          View and Run Code Online

          Please let me know if you find a mistake or if it fails for a specific case. I would love a chance to fix my code. Thank you.

          Reply Quote 0
            1 Reply Last reply

          • Padala Vamsi ujpNQUXGRi
            Padala Vamsi ujpNQUXGRi last edited by Padala Vamsi ujpNQUXGRi

            Thank you for the reply @Avan. I am the one who posted in codeproject but I haven't got the answer. I will check your code and reply back. Thank you for the code. 😊

            Reply Quote 1
              1 Reply Last reply

            • avan
              avan last edited by

              Hey @Padala-Vamsi-ujpNQUXGRi did you get a chance to test it? Just curious.

              Reply Quote 0
                1 Reply Last reply

              • Padala Vamsi ujpNQUXGRi
                Padala Vamsi ujpNQUXGRi last edited by

                Sorry, I am a full time employee, I'm little busy with work this week. Your solution may work. In codeproject some one answered the question and it seems to work. Thank you for replying to my question.

                Reply Quote 0
                  1 Reply Last reply

                • First post
                  Last post