Tasks Details
easy
1.
TieRopes
Tie adjacent ropes to achieve the maximum number of ropes of length >= K.
Task Score
100%
Correctness
100%
Performance
100%
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[0] = 1 A[1] = 2 A[2] = 3 A[3] = 4 A[4] = 1 A[5] = 1 A[6] = 3The ropes are shown in the figure below.
We can tie:
- rope 1 with rope 2 to produce a rope of length A[1] + A[2] = 5;
- rope 4 with rope 5 with rope 6 to produce a rope of length A[4] + A[5] + A[6] = 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[0] = 1 A[1] = 2 A[2] = 3 A[3] = 4 A[4] = 1 A[5] = 1 A[6] = 3the 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].
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 8
Total time used 30 minutes
Effective time used 30 minutes
Notes
not defined yet
Task timeline
Code: 17:12:12 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int K, int[] A) {
int sum = 0;
int count = 0;
for(int i = 0 ; i < A.length ; i++){
if(A[i] >= K) {
count++;
} else if(sum <= K){
sum = sum+A[i];
} else if(sum >= K){
sum = 0;
count++;
}
}
return count;
}
}
Analysis
expand all
Example tests
1.
0.014 s
WRONG ANSWER,
got 2 expected 3
Code: 17:15:24 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int K, int[] A) {
int sum = 0;
int count = 0;
for(int i = 0 ; i < A.length ; i++){
if(A[i] >= K) {
count++;
} else if(sum <= K){
sum = sum+A[i];
if(sum >= K){
sum = 0;
count++;
}
}
}
return count;
}
}
Analysis
Code: 17:16:34 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int K, int[] A) {
int sum = 0;
int count = 0;
for(int i = 0 ; i < A.length ; i++){
if(A[i] >= K) {
count++;
} else if(sum <= K){
sum = sum+A[i];
if(sum >= K){
sum = 0;
count++;
}
}
}
return count;
}
}
User test case 1:
[4, [9]]
User test case 2:
[5, [1, 1, 5, 1, 2, 5]]
User test case 3:
[7, [1, 1, 1, 1, 1, 1]]
Analysis
expand all
User tests
1.
0.013 s
OK
function result: 1
function result: 1
1.
0.013 s
OK
function result: 3
function result: 3
1.
0.015 s
OK
function result: 0
function result: 0
Code: 17:17:23 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int K, int[] A) {
int sum = 0;
int count = 0;
for(int i = 0 ; i < A.length ; i++){
if(A[i] >= K) {
count++;
sum = 0;
} else if(sum <= K){
sum = sum+A[i];
if(sum >= K){
sum = 0;
count++;
}
}
}
return count;
}
}
User test case 1:
[4, [9]]
User test case 2:
[5, [1, 1, 5, 1, 2, 5]]
User test case 3:
[7, [1, 1, 1, 1, 1, 1]]
Analysis
expand all
User tests
1.
0.013 s
OK
function result: 1
function result: 1
1.
0.014 s
OK
function result: 2
function result: 2
1.
0.014 s
OK
function result: 0
function result: 0
Code: 17:18:22 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int K, int[] A) {
int sum = 0;
int count = 0;
for(int i = 0 ; i < A.length ; i++){
if(A[i] >= K) {
count++;
sum = 0;
} else if(sum <= K){
sum = sum+A[i];
if(sum >= K){
sum = 0;
count++;
}
}
}
return count;
}
}
User test case 1:
[4, [9]]
User test case 2:
[5, [1, 1, 5, 1, 2, 5]]
User test case 3:
[7, [1, 1, 1, 1, 1, 1]]
User test case 4:
[1, [2, 9, 8, 7, 6, 5, 4, 3]]
Analysis
expand all
User tests
1.
0.017 s
OK
function result: 1
function result: 1
1.
0.014 s
OK
function result: 2
function result: 2
1.
0.013 s
OK
function result: 0
function result: 0
1.
0.014 s
OK
function result: 8
function result: 8
Code: 17:18:57 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int K, int[] A) {
int sum = 0;
int count = 0;
for(int i = 0 ; i < A.length ; i++){
if(A[i] >= K) {
count++;
sum = 0;
} else if(sum <= K){
sum = sum+A[i];
if(sum >= K){
sum = 0;
count++;
}
}
}
return count;
}
}
User test case 1:
[4, [9]]
User test case 2:
[5, [1, 1, 5, 1, 2, 5]]
User test case 3:
[7, [1, 1, 1, 1, 1, 1]]
User test case 4:
[1, [2, 9, 8, 7, 6, 5, 4, 3]]
Analysis
expand all
User tests
1.
0.013 s
OK
function result: 1
function result: 1
1.
0.015 s
OK
function result: 2
function result: 2
1.
0.013 s
OK
function result: 0
function result: 0
1.
0.014 s
OK
function result: 8
function result: 8
Code: 17:19:10 UTC,
java,
final,
score:
100
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int K, int[] A) {
int sum = 0;
int count = 0;
for(int i = 0 ; i < A.length ; i++){
if(A[i] >= K) {
count++;
sum = 0;
} else if(sum <= K){
sum = sum+A[i];
if(sum >= K){
sum = 0;
count++;
}
}
}
return count;
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.046 s
OK
2.
0.033 s
OK
3.
0.045 s
OK
4.
0.144 s
OK
5.
0.057 s
OK
1.
0.086 s
OK
2.
0.051 s
OK
3.
0.046 s
OK
4.
0.031 s
OK
5.
0.085 s
OK
1.
0.030 s
OK
2.
0.047 s
OK
1.
0.032 s
OK
2.
0.050 s
OK
expand all
Performance tests
1.
0.160 s
OK
2.
0.127 s
OK
3.
0.088 s
OK
1.
0.458 s
OK
2.
0.241 s
OK
3.
0.473 s
OK
1.
0.750 s
OK
2.
0.646 s
OK
3.
0.334 s
OK
4.
0.765 s
OK
1.
0.487 s
OK
2.
0.579 s
OK
3.
0.248 s
OK
4.
0.400 s
OK