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

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.

Nickel2018GoldenAward.png

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 [truefalsefalsetruefalse] is as follows:

PascalTriangle.png

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 = [truefalsefalsetruefalse], 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!

Nickel2018ResultScore.png

Happy coding,

J

Advertisements

3 thoughts on “Golden Hat-Trick, another Award for my Nickel 2018 solution

  1. 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

    Like

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

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s