Tasks Details
medium
Compute the number of "True" values in an OR-Pascal-triangle structure.
Task Score
60%
Correctness
100%
Performance
0%
On the sequence of logical values (true or false) we can build up an OR-Pascal-triangle structure. Instead of summing the values, as in a standard Pascal-triangle, we will combine them using the OR function. That means that the lowest row is simply the input sequence, and every entry in each subsequent row is the OR of the two elements below it. For example, the OR-Pascal-triangle built on the array [true, false, false, true, false] is as follows:
Your job is to count the number of nodes in the OR-Pascal-triangle that contain the value true (this number is 11 for the animation above).
Write a function:
class Solution { public int solution(boolean[] P); }
that, given an array P of N Booleans, returns the number of fields in the OR-Pascal-triangle built on P that contain the value true. If the result is greater than 1,000,000,000, your function should return 1,000,000,000.
Given P = [true, false, false, true, false], the function should return 11, as explained above.
Given P = [true, false, false, true], the function should return 7, as can be seen in the animation below.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 21
Time spent on task 41 minutes
Notes
not defined yet
Code: 15:13:12 UTC,
java,
autosave
Code: 15:50:41 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(boolean[] P) {
List<Boolean> out = new ArrayList<>();
for (boolean s: P) {
out.add(s);
}
int count = 0;
while (!out.isEmpty()){
if (out.get(0))
count++;
ArrayList<Boolean> newOut = new ArrayList<>();
for (int i = 1; i < out.size() - 1; i++) {
if (out.get(i))
count++;
if (out.get(i) || out.get(i + - 1)){
newOut.add(true);
}else{
newOut.add(false;
}
}
out = newOut;
}
return count;
}
}
Analysis
Compile error
Solution.java:25: error: ')' expected
newOut.add(false;
^
1 error
Code: 15:50:51 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(boolean[] P) {
List<Boolean> out = new ArrayList<>();
for (boolean s: P) {
out.add(s);
}
int count = 0;
while (!out.isEmpty()){
if (out.get(0))
count++;
ArrayList<Boolean> newOut = new ArrayList<>();
for (int i = 1; i < out.size() - 1; i++) {
if (out.get(i))
count++;
if (out.get(i) || out.get(i + - 1)){
newOut.add(true);
}else{
newOut.add(false);
}
}
out = newOut;
}
return count;
}
}
Analysis
Compile error
Solution.java:9: error: cannot find symbol
List<Boolean> out = new ArrayList<>();
^
symbol: class List
location: class Solution
Solution.java:9: error: cannot find symbol
List<Boolean> out = new ArrayList<>();
^
symbol: class ArrayList
location: class Solution
Solution.java:18: error: cannot find symbol
ArrayList<Boolean> newOut = new ArrayList<>();
^
symbol: class ArrayList
location: class Solution
Solution.java:18: error: cannot find symbol
ArrayList<Boolean> newOut = new ArrayList<>();
^
symbol: class ArrayList
location: class Solution
4 errors
Code: 15:51:07 UTC,
java,
verify,
result: Failed
import java.util.ArrayList;
import java.util.List;
class Solution {
public int solution(boolean[] P) {
List<Boolean> out = new ArrayList<>();
for (boolean s: P) {
out.add(s);
}
int count = 0;
while (!out.isEmpty()){
if (out.get(0))
count++;
ArrayList<Boolean> newOut = new ArrayList<>();
for (int i = 1; i < out.size() - 1; i++) {
if (out.get(i))
count++;
if (out.get(i) || out.get(i + - 1)){
newOut.add(true);
}else{
newOut.add(false);
}
}
out = newOut;
}
return count;
}
}
Analysis
expand all
Example tests
1.
0.008 s
WRONG ANSWER,
got 4 expected 11
1.
0.012 s
WRONG ANSWER,
got 2 expected 7
Code: 15:53:42 UTC,
java,
verify,
result: Passed
import java.util.ArrayList;
import java.util.List;
class Solution {
public int solution(boolean[] P) {
List<Boolean> out = new ArrayList<>();
for (boolean s: P) {
out.add(s);
}
int count = 0;
while (!out.isEmpty()){
if (out.get(0))
count++;
ArrayList<Boolean> newOut = new ArrayList<>();
for (int i = 1; i < out.size(); i++) {
if (out.get(i))
count++;
if (out.get(i) || out.get(i + - 1)){
newOut.add(true);
}else{
newOut.add(false);
}
}
out = newOut;
}
return count;
}
}
Analysis
Code: 15:53:48 UTC,
java,
verify,
result: Passed
import java.util.ArrayList;
import java.util.List;
class Solution {
public int solution(boolean[] P) {
List<Boolean> out = new ArrayList<>();
for (boolean s: P) {
out.add(s);
}
int count = 0;
while (!out.isEmpty()){
if (out.get(0))
count++;
ArrayList<Boolean> newOut = new ArrayList<>();
for (int i = 1; i < out.size(); i++) {
if (out.get(i))
count++;
if (out.get(i) || out.get(i + - 1)){
newOut.add(true);
}else{
newOut.add(false);
}
}
out = newOut;
}
return count;
}
}
Analysis
Code: 15:53:52 UTC,
java,
final,
score:
60
import java.util.ArrayList;
import java.util.List;
class Solution {
public int solution(boolean[] P) {
List<Boolean> out = new ArrayList<>();
for (boolean s: P) {
out.add(s);
}
int count = 0;
while (!out.isEmpty()){
if (out.get(0))
count++;
ArrayList<Boolean> newOut = new ArrayList<>();
for (int i = 1; i < out.size(); i++) {
if (out.get(i))
count++;
if (out.get(i) || out.get(i + - 1)){
newOut.add(true);
}else{
newOut.add(false);
}
}
out = newOut;
}
return count;
}
}Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N**2)
expand all
Correctness tests
1.
0.008 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
5.
0.004 s
OK
6.
0.008 s
OK
7.
0.008 s
OK
8.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
1.
0.012 s
OK
2.
0.012 s
OK
3.
0.012 s
OK
expand all
Performance tests
big_only_trues
Big tests, only True values.
Big tests, only True values.
✘
TIMEOUT ERROR
running time: >6.00 sec., time limit: 0.34 sec.
running time: >6.00 sec., time limit: 0.34 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.34 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.40 sec.
3.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.46 sec.
big_lonely_false
Big tests, no two neighbors False.
Big tests, no two neighbors False.
✘
TIMEOUT ERROR
running time: >6.00 sec., time limit: 0.34 sec.
running time: >6.00 sec., time limit: 0.34 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.34 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.38 sec.
3.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.50 sec.
big_random_tests
Big random tests.
Big random tests.
✘
TIMEOUT ERROR
running time: >6.00 sec., time limit: 0.26 sec.
running time: >6.00 sec., time limit: 0.26 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.26 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.26 sec.
3.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.26 sec.
4.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.27 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.66 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.62 sec.