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 4 minutes
Notes
not defined yet
Code: 05:51:05 UTC,
java,
autosave
Code: 05:51:59 UTC,
java,
autosave
// 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) {
// write your code in Java SE 8
var i = 0
var count = P.filter { $0 }.count
repeat{
if(P.count <= 1)
{
break
}
if P[i] || P[i + 1]
{
P[i] = true
}
i = i + 1
if(i == P.count - 1)
{
P.removeLast()
count = count + P.filter { $0 }.count
i = 0
}
}while(P.count > 1)
}
}
Code: 05:52:32 UTC,
java,
autosave
// 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) {
// write your code in Java SE 8
var i = 0
var count = P.filter { $0 }.count
repeat{
if(P.count <= 1)
{
break
}
if P[i] || P[i + 1]
{
P[i] = true
}
i = i + 1
if(i == P.count - 1)
{
P.removeLast()
count = count + P.filter { $0 }.count
i = 0
}
}while(P.count > 1)
}
}
Code: 05:52:37 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) {
// write your code in Java SE 8
var i = 0
var count = P.filter { $0 }.count
repeat{
if(P.count <= 1)
{
break
}
if P[i] || P[i + 1]
{
P[i] = true
}
i = i + 1
if(i == P.count - 1)
{
P.removeLast()
count = count + P.filter { $0 }.count
i = 0
}
}while(P.count > 1)
}
return count
}
Analysis
Compile error
Solution.java:10: error: ';' expected
var i = 0
^
Solution.java:11: error: ';' expected
var count = P.filter { $0 }.count
^
Solution.java:11: error: not a statement
var count = P.filter { $0 }.count
^
Solution.java:11: error: ';' expected
var count = P.filter { $0 }.count
^
Solution.java:11: error: illegal start of expression
var count = P.filter { $0 }.count
^
Solution.java:12: error: ';' expected
repeat{
^
Solution.java:15: error: ';' expected
break
^
Solution.java:17: error: '(' expected
if P[i] || P[i + 1]
^
Solution.java:17: error: ')' expected
if P[i] || P[i + 1]
^
Solution.java:19: error: ';' expected
P[i] = true
^
Solution.java:21: error: ';' expected
i = i + 1
^
Solution.java:24: error: ';' expected
P.removeLast()
^
Solution.java:25: error: ';' expected
count = count + P.filter { $0 }.count
^
Solution.java:25: error: not a statement
count = count + P.filter { $0 }.count
^
Solution.java:25: error: ';' expected
count = count + P.filter { $0 }.count
^
Solution.java:25: error: illegal start of expression
count = count + P.filter { $0 }.count
^
Solution.java:26: error: ';' expected
i = 0
^
Solution.java:30: error: illegal start of statement
}
^
Solution.java:31: error: illegal start of type
return count
^
Solution.java:31: error: ';' expected
return count
^
20 errors
Code: 05:52:48 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) {
// write your code in Java SE 8
var i = 0
var count = P.filter { $0 }.count
repeat{
if(P.count <= 1)
{
break
}
if P[i] || P[i + 1]
{
P[i] = true
}
i = i + 1
if(i == P.count - 1)
{
P.removeLast()
count = count + P.filter { $0 }.count
i = 0
}
}while(P.count > 1)
return count
}
Analysis
Compile error
Solution.java:10: error: ';' expected
var i = 0
^
Solution.java:11: error: ';' expected
var count = P.filter { $0 }.count
^
Solution.java:11: error: not a statement
var count = P.filter { $0 }.count
^
Solution.java:11: error: ';' expected
var count = P.filter { $0 }.count
^
Solution.java:11: error: illegal start of expression
var count = P.filter { $0 }.count
^
Solution.java:12: error: ';' expected
repeat{
^
Solution.java:15: error: ';' expected
break
^
Solution.java:17: error: '(' expected
if P[i] || P[i + 1]
^
Solution.java:17: error: ')' expected
if P[i] || P[i + 1]
^
Solution.java:19: error: ';' expected
P[i] = true
^
Solution.java:21: error: ';' expected
i = i + 1
^
Solution.java:24: error: ';' expected
P.removeLast()
^
Solution.java:25: error: ';' expected
count = count + P.filter { $0 }.count
^
Solution.java:25: error: not a statement
count = count + P.filter { $0 }.count
^
Solution.java:25: error: ';' expected
count = count + P.filter { $0 }.count
^
Solution.java:25: error: illegal start of expression
count = count + P.filter { $0 }.count
^
Solution.java:26: error: ';' expected
i = 0
^
Solution.java:30: error: ';' expected
return count
^
Solution.java:31: error: reached end of file while parsing
}
^
19 errors
Code: 05:53:05 UTC,
java,
autosave
// 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) {
// write your code in Java SE 8
var i = 0
var count = P.filter { $0 }.count
repeat{
if(P.count <= 1)
{
break
}
if P[i] || P[i + 1]
{
P[i] = true
}
i = i + 1
if(i == P.count - 1)
{
P.removeLast()
count = count + P.filter { $0 }.count
i = 0
}
}while(P.count > 1)
return count
}
Code: 05:53:08 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) {
// write your code in Java SE 8
var i = 0
var count = P.filter { $0 }.count
repeat{
if(P.count <= 1)
{
break
}
if P[i] || P[i + 1]
{
P[i] = true
}
i = i + 1
if(i == P.count - 1)
{
P.removeLast()
count = count + P.filter { $0 }.count
i = 0
}
}while(P.count > 1)
return count
}
Analysis
Compile error
Solution.java:10: error: ';' expected
var i = 0
^
Solution.java:11: error: ';' expected
var count = P.filter { $0 }.count
^
Solution.java:11: error: not a statement
var count = P.filter { $0 }.count
^
Solution.java:11: error: ';' expected
var count = P.filter { $0 }.count
^
Solution.java:11: error: illegal start of expression
var count = P.filter { $0 }.count
^
Solution.java:12: error: ';' expected
repeat{
^
Solution.java:15: error: ';' expected
break
^
Solution.java:17: error: '(' expected
if P[i] || P[i + 1]
^
Solution.java:17: error: ')' expected
if P[i] || P[i + 1]
^
Solution.java:19: error: ';' expected
P[i] = true
^
Solution.java:21: error: ';' expected
i = i + 1
^
Solution.java:24: error: ';' expected
P.removeLast()
^
Solution.java:25: error: ';' expected
count = count + P.filter { $0 }.count
^
Solution.java:25: error: not a statement
count = count + P.filter { $0 }.count
^
Solution.java:25: error: ';' expected
count = count + P.filter { $0 }.count
^
Solution.java:25: error: illegal start of expression
count = count + P.filter { $0 }.count
^
Solution.java:26: error: ';' expected
i = 0
^
Solution.java:30: error: ';' expected
return count
^
Solution.java:31: error: reached end of file while parsing
}
^
19 errors
Code: 05:53:16 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) {
// write your code in Java SE 8
var i = 0
var count = P.filter { $0 }.count
repeat{
if(P.count <= 1)
{
break
}
if P[i] || P[i + 1]
{
P[i] = true
}
i = i + 1
if(i == P.count - 1)
{
P.removeLast()
count = count + P.filter { $0 }.count
i = 0
}
}while(P.count > 1)
return count
}
Analysis
Compile error
Solution.java:10: error: ';' expected
var i = 0
^
Solution.java:11: error: ';' expected
var count = P.filter { $0 }.count
^
Solution.java:11: error: not a statement
var count = P.filter { $0 }.count
^
Solution.java:11: error: ';' expected
var count = P.filter { $0 }.count
^
Solution.java:11: error: illegal start of expression
var count = P.filter { $0 }.count
^
Solution.java:12: error: ';' expected
repeat{
^
Solution.java:15: error: ';' expected
break
^
Solution.java:17: error: '(' expected
if P[i] || P[i + 1]
^
Solution.java:17: error: ')' expected
if P[i] || P[i + 1]
^
Solution.java:19: error: ';' expected
P[i] = true
^
Solution.java:21: error: ';' expected
i = i + 1
^
Solution.java:24: error: ';' expected
P.removeLast()
^
Solution.java:25: error: ';' expected
count = count + P.filter { $0 }.count
^
Solution.java:25: error: not a statement
count = count + P.filter { $0 }.count
^
Solution.java:25: error: ';' expected
count = count + P.filter { $0 }.count
^
Solution.java:25: error: illegal start of expression
count = count + P.filter { $0 }.count
^
Solution.java:26: error: ';' expected
i = 0
^
Solution.java:30: error: ';' expected
return count
^
Solution.java:31: error: reached end of file while parsing
}
^
19 errors
Code: 05:53:23 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) {
// write your code in Java SE 8
var i = 0
var count = P.filter { $0 }.count
repeat{
if(P.count <= 1)
{
break
}
if P[i] || P[i + 1]
{
P[i] = true
}
i = i + 1
if(i == P.count - 1)
{
P.removeLast()
count = count + P.filter { $0 }.count
i = 0
}
}while(P.count > 1)
return count
}
Analysis
Compile error
Solution.java:10: error: ';' expected
var i = 0
^
Solution.java:11: error: ';' expected
var count = P.filter { $0 }.count
^
Solution.java:11: error: not a statement
var count = P.filter { $0 }.count
^
Solution.java:11: error: ';' expected
var count = P.filter { $0 }.count
^
Solution.java:11: error: illegal start of expression
var count = P.filter { $0 }.count
^
Solution.java:12: error: ';' expected
repeat{
^
Solution.java:15: error: ';' expected
break
^
Solution.java:17: error: '(' expected
if P[i] || P[i + 1]
^
Solution.java:17: error: ')' expected
if P[i] || P[i + 1]
^
Solution.java:19: error: ';' expected
P[i] = true
^
Solution.java:21: error: ';' expected
i = i + 1
^
Solution.java:24: error: ';' expected
P.removeLast()
^
Solution.java:25: error: ';' expected
count = count + P.filter { $0 }.count
^
Solution.java:25: error: not a statement
count = count + P.filter { $0 }.count
^
Solution.java:25: error: ';' expected
count = count + P.filter { $0 }.count
^
Solution.java:25: error: illegal start of expression
count = count + P.filter { $0 }.count
^
Solution.java:26: error: ';' expected
i = 0
^
Solution.java:30: error: ';' expected
return count
^
Solution.java:31: error: reached end of file while parsing
}
^
19 errors
Code: 05:54:05 UTC,
swift3,
autosave
import Foundation
import Glibc
// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
public func solution(_ P : inout [Bool]) -> Int {
// write your code in Swift 3.0 (Linux)
var i = 0
var count = P.filter { $0 }.count
repeat
{
if(P.count <= 1)
{
break
}
if P[i] || P[i + 1]
{
P[i] = true
}
i = i + 1
if(i == P.count - 1)
{
P.removeLast()
count = count + P.filter { $0 }.count
i = 0
}
}while(P.count > 1)
}
Code: 05:54:16 UTC,
swift3,
autosave
import Foundation
import Glibc
// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
public func solution(_ P : inout [Bool]) -> Int {
// write your code in Swift 3.0 (Linux)
var i = 0
var count = P.filter { $0 }.count
repeat
{
if(P.count <= 1)
{
break
}
if P[i] || P[i + 1]
{
P[i] = true
}
i = i + 1
if(i == P.count - 1)
{
P.removeLast()
count = count + P.filter { $0 }.count
i = 0
}
}while(P.count > 1)
}
Code: 05:54:26 UTC,
swift3,
verify,
result: Passed
import Foundation
import Glibc
// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
public func solution(_ P : inout [Bool]) -> Int {
// write your code in Swift 3.0 (Linux)
var i = 0
var count = P.filter { $0 }.count
repeat
{
if(P.count <= 1)
{
break
}
if P[i] || P[i + 1]
{
P[i] = true
}
i = i + 1
if(i == P.count - 1)
{
P.removeLast()
count = count + P.filter { $0 }.count
i = 0
}
}while(P.count > 1)
return count
}
Analysis
Code: 05:54:31 UTC,
swift3,
verify,
result: Passed
import Foundation
import Glibc
// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
public func solution(_ P : inout [Bool]) -> Int {
// write your code in Swift 3.0 (Linux)
var i = 0
var count = P.filter { $0 }.count
repeat
{
if(P.count <= 1)
{
break
}
if P[i] || P[i + 1]
{
P[i] = true
}
i = i + 1
if(i == P.count - 1)
{
P.removeLast()
count = count + P.filter { $0 }.count
i = 0
}
}while(P.count > 1)
return count
}
Analysis
Code: 05:54:34 UTC,
swift3,
final,
score:
60
import Foundation
import Glibc
// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
public func solution(_ P : inout [Bool]) -> Int {
// write your code in Swift 3.0 (Linux)
var i = 0
var count = P.filter { $0 }.count
repeat
{
if(P.count <= 1)
{
break
}
if P[i] || P[i + 1]
{
P[i] = true
}
i = i + 1
if(i == P.count - 1)
{
P.removeLast()
count = count + P.filter { $0 }.count
i = 0
}
}while(P.count > 1)
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.028 s
OK
2.
0.028 s
OK
3.
0.028 s
OK
4.
0.032 s
OK
5.
0.028 s
OK
6.
0.028 s
OK
7.
0.028 s
OK
8.
0.028 s
OK
1.
0.028 s
OK
2.
0.028 s
OK
3.
0.028 s
OK
1.
0.028 s
OK
2.
0.028 s
OK
3.
0.028 s
OK
1.
0.028 s
OK
2.
0.028 s
OK
3.
0.032 s
OK
1.
0.032 s
OK
2.
0.032 s
OK
3.
0.028 s
OK
1.
0.032 s
OK
2.
0.032 s
OK
3.
0.032 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.16 sec.
running time: >6.00 sec., time limit: 0.16 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.16 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.18 sec.
3.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.19 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.18 sec.
running time: >6.00 sec., time limit: 0.18 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.18 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.18 sec.
3.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.19 sec.
big_random_tests
Big random tests.
Big random tests.
✘
TIMEOUT ERROR
running time: >6.00 sec., time limit: 0.16 sec.
running time: >6.00 sec., time limit: 0.16 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.16 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.16 sec.
3.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.16 sec.
4.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.16 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.22 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.22 sec.