Test results - Codility

Tasks Details

medium

1. MinMaxDivision

Divide array A into K blocks and minimize the largest sum of any block.

Task Score

100%

Correctness

100%

Performance

100%

You are given integers K, M and a non-empty array A consisting of N integers. Every element of the array is not greater than M.

You should divide this array into K blocks of consecutive elements. The size of the block is any integer between 0 and N. Every element of the array should belong to some block.

The sum of the block from X to Y equals A[X] + A[X + 1] + ... + A[Y]. The sum of empty block equals 0.

The large sum is the maximal sum of any block.

For example, you are given integers K = 3, M = 5 and array A such that:

A[0] = 2 A[1] = 1 A[2] = 5 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 2

The array can be divided, for example, into the following blocks:

[2, 1, 5, 1, 2, 2, 2], [], [] with a large sum of 15;

[2], [1, 5, 1, 2], [2, 2] with a large sum of 9;

[2, 1, 5], [], [1, 2, 2, 2] with a large sum of 8;

[2, 1], [5, 1], [2, 2, 2] with a large sum of 6.

The goal is to minimize the large sum. In the above example, 6 is the minimal large sum.

Write a function:

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

that, given integers K, M and a non-empty array A consisting of N integers, returns the minimal large sum.

For example, given K = 3, M = 5 and array A such that:

A[0] = 2 A[1] = 1 A[2] = 5 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 2

the function should return 6, as explained above.

Write an efficient algorithm for the following assumptions:

N and K are integers within the range [1..100,000];

M is an integer within the range [0..10,000];

each element of array A is an integer within the range [0..M].

Solution

Programming language used Java 8

Time spent on task 2 minutes

Notes

not defined yet

Code: 07:28:00 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// 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 M, int[] A) {
        // write your code in Java SE 8
    }
}

Code: 07:28:10 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

import java.util.*;

class Solution {
    public int solution(int K, int M, int[] A) {
         public int solution(int K, int M, int[] A) {
             int low = Arrays.stream(A).max().getAsInt();
             int up = Arrays.stream(A).sum();
             int res = up;
 
             while (low <= up) {
                 int mid = (low + up) / 2;
                 if (isDivision(K, mid, A)) {
                     res = mid;
                     up = mid - 1;
                 } else {
                     low = mid + 1;
                 }
             }
 
             return res;
         }
 
         private boolean isDivision(int K, int target, int[] A) {
             int sum = 0;
             int count = 1;
             for (int a : A) {
                 sum += a;
                 if (sum > target) {
                     sum = a;
                     count++;
                 }
 
                 if (count > K) return false;
             }
 
             return true;
         }
    }
}

Code: 07:28:32 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

import java.util.*;

class Solution {
    public int solution(int K, int M, int[] A) {
        public int solution(int K, int M, int[] A) {
	int low = Arrays.stream(A).max().getAsInt();
	int up = Arrays.stream(A).sum();
	int res = up;

	while (low <= up) {
		int mid = (low + up) / 2;
		if (isDivision(K, mid, A)) {
			res = mid;
			up = mid - 1;
		} else {
			low = mid + 1;
		}
	}

	return res;
}

private boolean isDivision(int K, int target, int[] A) {
	int sum = 0;
	int count = 1;
	for (int a: A) {
		sum += a;
		if (sum > target) {
			sum = a;
			count++;
		}

		if (count > K) return false;
	}

	return true;
}
    }
}

Code: 07:28:42 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

import java.util.*;

class Solution {
    public int solution(int K, int M, int[] A) {
        public int solution(int K, int M, int[] A) {
    	int low = Arrays.stream(A).max().getAsInt();
    	int up = Arrays.stream(A).sum();
    	int res = up;
    
    	while (low <= up) {
    		int mid = (low + up) / 2;
    		if (isDivision(K, mid, A)) {
    			res = mid;
    			up = mid - 1;
    		} else {
    			low = mid + 1;
    		}
    	}
    
    	return res;
    }
    
    private boolean isDivision(int K, int target, int[] A) {
    	int sum = 0;
    	int count = 1;
    	for (int a: A) {
    		sum += a;
    		if (sum > target) {
    			sum = a;
    			count++;
    		}
    
    		if (count > K) return false;
    	}
    
    	return true;
    }
}

Analysis

Compile error

Solution.java:5: error: illegal start of expression
        public int solution(int K, int M, int[] A) {
        ^
Solution.java:5: error: ';' expected
        public int solution(int K, int M, int[] A) {
                           ^
Solution.java:5: error: <identifier> expected
        public int solution(int K, int M, int[] A) {
                                  ^
Solution.java:5: error: not a statement
        public int solution(int K, int M, int[] A) {
                                       ^
Solution.java:5: error: ';' expected
        public int solution(int K, int M, int[] A) {
                                        ^
Solution.java:5: error: ';' expected
        public int solution(int K, int M, int[] A) {
                                                 ^
Solution.java:23: error: illegal start of expression
    private boolean isDivision(int K, int target, int[] A) {
    ^
Solution.java:23: error: ';' expected
    private boolean isDivision(int K, int target, int[] A) {
                              ^
Solution.java:23: error: <identifier> expected
    private boolean isDivision(int K, int target, int[] A) {
                                     ^
Solution.java:23: error: not a statement
    private boolean isDivision(int K, int target, int[] A) {
                                          ^
Solution.java:23: error: ';' expected
    private boolean isDivision(int K, int target, int[] A) {
                                                ^
Solution.java:23: error: ';' expected
    private boolean isDivision(int K, int target, int[] A) {
                                                         ^
Solution.java:38: error: reached end of file while parsing
}
 ^
13 errors

Code: 07:29:02 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

import java.util.*;

class Solution {
    
    public int solution(int K, int M, int[] A) {
        public int solution(int K, int M, int[] A) {
    	int low = Arrays.stream(A).max().getAsInt();
    	int up = Arrays.stream(A).sum();
    	int res = up;
    
    	while (low <= up) {
    		int mid = (low + up) / 2;
    		if (isDivision(K, mid, A)) {
    			res = mid;
    			up = mid - 1;
    		} else {
    			low = mid + 1;
    		}
    	}
    
    	return res;
    }
    
    private boolean isDivision(int K, int target, int[] A) {
    	int sum = 0;
    	int count = 1;
    	for (int a: A) {
    		sum += a;
    		if (sum > target) {
    			sum = a;
    			count++;
    		}
    
    		if (count > K) return false;
    	}
    
    	return true;
    }
}

Code: 07:29:16 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7

import java.util.*;

class Solution {
    public int solution(int K, int M, int[] A) {
        // write your code in Java SE 8
    }
}

Code: 07:29:27 UTC, java, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

import java.util.*;

class Solution {
    public int solution(int K, int M, int[] A) {
    	int low = Arrays.stream(A).max().getAsInt();
    	int up = Arrays.stream(A).sum();
    	int res = up;
    
    	while (low <= up) {
    		int mid = (low + up) / 2;
    		if (isDivision(K, mid, A)) {
    			res = mid;
    			up = mid - 1;
    		} else {
    			low = mid + 1;
    		}
    	}
    
    	return res;
    }
    
    private boolean isDivision(int K, int target, int[] A) {
    	int sum = 0;
    	int count = 1;
    	for (int a: A) {
    		sum += a;
    		if (sum > target) {
    			sum = a;
    			count++;
    		}
    
    		if (count > K) return false;
    	}
    
    	return true;
    }
}

Analysis

expand all Example tests

▶

example
example test

✔

0.088 s

Code: 07:29:32 UTC, java, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

import java.util.*;

class Solution {
    public int solution(int K, int M, int[] A) {
    	int low = Arrays.stream(A).max().getAsInt();
    	int up = Arrays.stream(A).sum();
    	int res = up;
    
    	while (low <= up) {
    		int mid = (low + up) / 2;
    		if (isDivision(K, mid, A)) {
    			res = mid;
    			up = mid - 1;
    		} else {
    			low = mid + 1;
    		}
    	}
    
    	return res;
    }
    
    private boolean isDivision(int K, int target, int[] A) {
    	int sum = 0;
    	int count = 1;
    	for (int a: A) {
    		sum += a;
    		if (sum > target) {
    			sum = a;
    			count++;
    		}
    
    		if (count > K) return false;
    	}
    
    	return true;
    }
}

Analysis

expand all Example tests

▶

example
example test

✔

0.088 s

Code: 07:29:36 UTC, java, final, score: 100

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

import java.util.*;

class Solution {
    public int solution(int K, int M, int[] A) {
    	int low = Arrays.stream(A).max().getAsInt();
    	int up = Arrays.stream(A).sum();
    	int res = up;
    
    	while (low <= up) {
    		int mid = (low + up) / 2;
    		if (isDivision(K, mid, A)) {
    			res = mid;
    			up = mid - 1;
    		} else {
    			low = mid + 1;
    		}
    	}
    
    	return res;
    }
    
    private boolean isDivision(int K, int target, int[] A) {
    	int sum = 0;
    	int count = 1;
    	for (int a: A) {
    		sum += a;
    		if (sum > target) {
    			sum = a;
    			count++;
    		}
    
    		if (count > K) return false;
    	}
    
    	return true;
    }
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N*log(N+M))

expand all Example tests

▶

example
example test

✔

0.092 s

expand all Correctness tests

▶

extreme_single
single elements

✔

0.088 s

▶

extreme_double
single and double elements

✔

0.088 s

▶

extreme_min_max
maximal / minimal values

✔

0.088 s

0.092 s

0.088 s

0.092 s

▶

simple1
simple tests

✔

0.088 s

▶

simple2
simple tests

✔

0.088 s

▶

tiny_random_ones
random values {0, 1}, N = 100

✔

0.088 s

0.092 s

0.096 s

0.088 s

expand all Performance tests

▶

small_random_ones
random values {0, 1}, N = 100

✔

0.088 s

0.092 s

0.088 s

▶

medium_zeros
many zeros and 99 in the middle, length = 15,000

✔

0.124 s

0.128 s

▶

medium_random
random values {1, 100}, N = 20,000

✔

0.140 s

0.136 s

0.140 s

▶

large_random
random values {0, ..., MAX_INT}, N = 100,000

✔

0.416 s

0.420 s

▶

large_random_ones
random values {0, 1}, N = 100,000

✔

0.320 s

0.316 s

0.320 s

0.316 s

▶

all_the_same
all the same values, N = 100,000

✔

0.444 s

0.440 s

0.444 s