Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

#### TieRopes

Tie adjacent ropes to achieve the maximum number of ropes of length >= K.

There are N ropes numbered from 0 to N − 1, whose lengths are given in an array A, lying on the floor in a line. For each I (0 ≤ I < N), the length of rope I on the line is A[I].

We say that two ropes I and I + 1 are adjacent. Two adjacent ropes can be tied together with a knot, and the length of the tied rope is the sum of lengths of both ropes. The resulting new rope can then be tied again.

For a given integer K, the goal is to tie the ropes in such a way that the number of ropes whose length is greater than or equal to K is maximal.

For example, consider K = 4 and array A such that:

A = 1 A = 2 A = 3 A = 4 A = 1 A = 1 A = 3

The ropes are shown in the figure below. We can tie:

• rope 1 with rope 2 to produce a rope of length A + A = 5;
• rope 4 with rope 5 with rope 6 to produce a rope of length A + A + A = 5.

After that, there will be three ropes whose lengths are greater than or equal to K = 4. It is not possible to produce four such ropes.

Write a function:

class Solution { public int solution(int K, int[] A); }

that, given an integer K and a non-empty array A of N integers, returns the maximum number of ropes of length greater than or equal to K that can be created.

For example, given K = 4 and array A such that:

A = 1 A = 2 A = 3 A = 4 A = 1 A = 1 A = 3

the function should return 3, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• K is an integer within the range [1..1,000,000,000];
• each element of array A is an integer within the range [1..1,000,000,000].
{"ft_lang_label":"__label__en","ft_lang_prob":0.8931478,"math_prob":0.9987099,"size":29173,"snap":"2021-31-2021-39","text_gpt3_token_len":9047,"char_repetition_ratio":0.15276492,"word_repetition_ratio":0.9747699,"special_character_ratio":0.3451479,"punctuation_ratio":0.11977133,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99778694,"pos_list":[0,1,2],"im_url_duplicate_count":[null,6,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-09-16T18:38:17Z\",\"WARC-Record-ID\":\"<urn:uuid:1679b26c-7d76-4a9d-9f37-0e7426213c21>\",\"Content-Length\":\"75831\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:109907ec-aafd-4a63-a3f4-4af371e74721>\",\"WARC-Concurrent-To\":\"<urn:uuid:f98c2ece-a57f-437c-9ce8-c484723c428f>\",\"WARC-IP-Address\":\"52.71.87.144\",\"WARC-Target-URI\":\"https://app.codility.com/programmers/lessons/16-greedy_algorithms/tie_ropes/\",\"WARC-Payload-Digest\":\"sha1:BYXSQPYTCYCM7OGLU2G6T5XGK6CTPSYQ\",\"WARC-Block-Digest\":\"sha1:FJ6XHASXEVNYLY4RNX4RGDIEJ4IBYJDJ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-39/CC-MAIN-2021-39_segments_1631780053717.37_warc_CC-MAIN-20210916174455-20210916204455-00399.warc.gz\"}"}