This was the third **Codility Challenge** this year and for the third time I’m getting Golden Award for my solution. After the Ferrum 2018 and Cobaltum 2018, this award is for the current challenge **Nickel 2018**. This time I got the solution in my head as soon as I read the assignment and I was doing that while holding a screaming baby in my hand and my 2-year old was destroying the living room in the background. With this task I felt like I wasn’t challenged properly.

Also I didn’t need to solve this in Visual Studio which is the environment that I’m used to and I use to solve these challenges.

This one was sponsored by a company named **Avature** so maybe they had specific needs and they will use this challenge to make a talent pool for their need.

## The Nickel 2018 Challenge

This challenge uses a boolean input array (values are either true or false) and on top of that is build an OR-Pascal-triangle. Instead of summing the values as in the standard Pascal triangle, we are combining 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.

Assume that:

- N is an integer within the range [1..100,000].

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Try this challenge by yourself and get these results to get your Golden Award!

Happy coding,

J

Hi Jord,

I came up with a solution for this and only got 60% correctness. I have no idea why my solution doesn’t work for other test cases. I used the concept of fibonacci sequences to arrive at an answer. Is that how you solved the challenge to? any hint is greatly appreciated.

Mohan

LikeLike

I solved it with Task Score 90% Correctness 100% and Performance 75% in one attempt. However, all next attempts did not improve it.

LikeLike

[…] Golden Hat-Trick, another Award for my Nickel 2018 solution […]

LikeLike