Test results - Codility

Tasks Details

medium

1. PascalTriangle

Compute the number of "True" values in an OR-Pascal-triangle structure.

Task Score

90%

Correctness

100%

Performance

75%

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

Solution

Programming language used Java 8

Time spent on task 2 minutes

Notes

not defined yet

Code: 18:44:26 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(boolean[] P) {
        // write your code in Java SE 8
    }
}

Code: 18:44:36 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104

package com.PJ;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.Assert.assertEquals;

/**
 *
 */
public class Challenge_2018_03_Nickel2018 {

  private static int MAX_RESULT = 1_000_000_000;
  private static int MAX_NODES_FOR_MAX_RESULT = 44720;

  @Test
  void test() {
    // regular cases
    assertEquals(7, solution(new boolean[]{true, false, false, true}));
    assertEquals(11, solution(new boolean[]{true, false, false, true, false}));
    assertEquals(8, solution(new boolean[]{true, false, true, false}));

    // corner cases
    assertEquals(0, solution(new boolean[]{false, false, false, false}));
    assertEquals(10, solution(new boolean[]{true, true, true, true}));
  }

  @Test
  void test_huge_corner_cases() {
    boolean[] bigArray = new boolean[4_000];
    Arrays.fill(bigArray, true);
    assertEquals(8_002_000, solution(bigArray));

    boolean[] largeArray = new boolean[10_000];
    Arrays.fill(largeArray, true);
    assertEquals(50_005_000, solution(largeArray));

    boolean[] hugeArray = new boolean[50_000];
    Arrays.fill(hugeArray, true);
    assertEquals(MAX_RESULT, solution(hugeArray));

    boolean[] hugeArrayFalse = new boolean[50_000];
    Arrays.fill(hugeArrayFalse, false);
    assertEquals(0, solution(hugeArrayFalse));
  }

  private int solution(boolean[] P) {
    int result = 0;

    for (int i = 0; i < P.length; i++) {
      if (P[i]) {
        result++;
      }
    }
    result += calculateRow(P);

    return (result >= 0 && result < MAX_RESULT) ? result : MAX_RESULT;
  }


  private int calculateRow(boolean[] row) {
    int result = 0;

    boolean[] upperRow = new boolean[row.length - 1];

    for (int i = 0; i < row.length - 1; i++) {
      boolean product = row[i] || row[i + 1];
      upperRow[i] = product;
      if (product) {
        result++;
      }
    }

    if (result == 0) {
      return result;

    } else if (result == row.length - 1) {
      if (result > MAX_NODES_FOR_MAX_RESULT) {
        return MAX_RESULT;
      } else {
        return result + countAllNodesAbove(result);
      }

    } else {
      result += calculateRow(upperRow);

      if (result > MAX_RESULT) {
        return MAX_RESULT;
      }
    }

    return result;
  }

  private int countAllNodesAbove(int count) {
    if (count > MAX_NODES_FOR_MAX_RESULT) {
      return MAX_RESULT;
    } else {
      return (count)*(count - 1)/2;
    }
  }

}

Code: 18:44:43 UTC, java, autosave

show code in pop-up

package com.PJ;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.Assert.assertEquals;

/**
 *
 */
public class Solution {

  private static int MAX_RESULT = 1_000_000_000;
  private static int MAX_NODES_FOR_MAX_RESULT = 44720;

  @Test
  void test() {
    // regular cases
    assertEquals(7, solution(new boolean[]{true, false, false, true}));
    assertEquals(11, solution(new boolean[]{true, false, false, true, false}));
    assertEquals(8, solution(new boolean[]{true, false, true, false}));

    // corner cases
    assertEquals(0, solution(new boolean[]{false, false, false, false}));
    assertEquals(10, solution(new boolean[]{true, true, true, true}));
  }

  @Test
  void test_huge_corner_cases() {
    boolean[] bigArray = new boolean[4_000];
    Arrays.fill(bigArray, true);
    assertEquals(8_002_000, solution(bigArray));

    boolean[] largeArray = new boolean[10_000];
    Arrays.fill(largeArray, true);
    assertEquals(50_005_000, solution(largeArray));

    boolean[] hugeArray = new boolean[50_000];
    Arrays.fill(hugeArray, true);
    assertEquals(MAX_RESULT, solution(hugeArray));

    boolean[] hugeArrayFalse = new boolean[50_000];
    Arrays.fill(hugeArrayFalse, false);
    assertEquals(0, solution(hugeArrayFalse));
  }

  private int solution(boolean[] P) {
    int result = 0;

    for (int i = 0; i < P.length; i++) {
      if (P[i]) {
        result++;
      }
    }
    result += calculateRow(P);

    return (result >= 0 && result < MAX_RESULT) ? result : MAX_RESULT;
  }


  private int calculateRow(boolean[] row) {
    int result = 0;

    boolean[] upperRow = new boolean[row.length - 1];

    for (int i = 0; i < row.length - 1; i++) {
      boolean product = row[i] || row[i + 1];
      upperRow[i] = product;
      if (product) {
        result++;
      }
    }

    if (result == 0) {
      return result;

    } else if (result == row.length - 1) {
      if (result > MAX_NODES_FOR_MAX_RESULT) {
        return MAX_RESULT;
      } else {
        return result + countAllNodesAbove(result);
      }

    } else {
      result += calculateRow(upperRow);

      if (result > MAX_RESULT) {
        return MAX_RESULT;
      }
    }

    return result;
  }

  private int countAllNodesAbove(int count) {
    if (count > MAX_NODES_FOR_MAX_RESULT) {
      return MAX_RESULT;
    } else {
      return (count)*(count - 1)/2;
    }
  }

}

Code: 18:44:53 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

package com.PJ;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.Assert.assertEquals;

/**
 *
 */
public class Solution {

  private static int MAX_RESULT = 1_000_000_000;
  private static int MAX_NODES_FOR_MAX_RESULT = 44720;

  public int solution(boolean[] P) {
    int result = 0;

    for (int i = 0; i < P.length; i++) {
      if (P[i]) {
        result++;
      }
    }
    result += calculateRow(P);

    return (result >= 0 && result < MAX_RESULT) ? result : MAX_RESULT;
  }


  private int calculateRow(boolean[] row) {
    int result = 0;

    boolean[] upperRow = new boolean[row.length - 1];

    for (int i = 0; i < row.length - 1; i++) {
      boolean product = row[i] || row[i + 1];
      upperRow[i] = product;
      if (product) {
        result++;
      }
    }

    if (result == 0) {
      return result;

    } else if (result == row.length - 1) {
      if (result > MAX_NODES_FOR_MAX_RESULT) {
        return MAX_RESULT;
      } else {
        return result + countAllNodesAbove(result);
      }

    } else {
      result += calculateRow(upperRow);

      if (result > MAX_RESULT) {
        return MAX_RESULT;
      }
    }

    return result;
  }

  private int countAllNodesAbove(int count) {
    if (count > MAX_NODES_FOR_MAX_RESULT) {
      return MAX_RESULT;
    } else {
      return (count)*(count - 1)/2;
    }
  }

}

Code: 18:44:56 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

public class Solution {

  private static int MAX_RESULT = 1_000_000_000;
  private static int MAX_NODES_FOR_MAX_RESULT = 44720;

  public int solution(boolean[] P) {
    int result = 0;

    for (int i = 0; i < P.length; i++) {
      if (P[i]) {
        result++;
      }
    }
    result += calculateRow(P);

    return (result >= 0 && result < MAX_RESULT) ? result : MAX_RESULT;
  }


  private int calculateRow(boolean[] row) {
    int result = 0;

    boolean[] upperRow = new boolean[row.length - 1];

    for (int i = 0; i < row.length - 1; i++) {
      boolean product = row[i] || row[i + 1];
      upperRow[i] = product;
      if (product) {
        result++;
      }
    }

    if (result == 0) {
      return result;

    } else if (result == row.length - 1) {
      if (result > MAX_NODES_FOR_MAX_RESULT) {
        return MAX_RESULT;
      } else {
        return result + countAllNodesAbove(result);
      }

    } else {
      result += calculateRow(upperRow);

      if (result > MAX_RESULT) {
        return MAX_RESULT;
      }
    }

    return result;
  }

  private int countAllNodesAbove(int count) {
    if (count > MAX_NODES_FOR_MAX_RESULT) {
      return MAX_RESULT;
    } else {
      return (count)*(count - 1)/2;
    }
  }

}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.004 s

▶

example2
Second example test.

✔

0.004 s

Code: 18:45:37 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

public class Solution {

  private static int MAX_RESULT = 1_000_000_000;
  private static int MNODES_FOR_MAX_RESULT = 44720;

  public int solution(boolean[] P) {
    int result = 0;

    for (int i = 0; i < P.length; i++) {
      if (P[i]) {
        result++;
      }
    }
    result += calculateRow(P);

    return (result >= 0 && result < MAX_RESULT) ? result : MAX_RESULT;
  }


  private int calculateRow(boolean[] row) {
    int result = 0;

    boolean[] upperRow = new boolean[row.length - 1];

    for (int i = 0; i < row.length - 1; i++) {
      boolean product = row[i] || row[i + 1];
      upperRow[i] = product;
      if (product) {
        result++;
      }
    }

    if (result == 0) {
      return result;

    } else if (result == row.length - 1) {
      if (result > MAX_NODES_FOR_MAX_RESULT) {
        return MAX_RESULT;
      } else {
        return result + countAllNodesAbove(result);
      }

    } else {
      result += calculateRow(upperRow);

      if (result > MAX_RESULT) {
        return MAX_RESULT;
      }
    }

    return result;
  }

  private int countAllNodesAbove(int count) {
    if (count > MAX_NODES_FOR_MAX_RESULT) {
      return MAX_RESULT;
    } else {
      return (count)*(count - 1)/2;
    }
  }

}

Code: 18:45:47 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

public class Solution {

  private static int MAX_RESULT = 1_000_000_000;
  private static int NODES_FOR_MAX_RESULT = 44720;

  public int solution(boolean[] P) {
    int result = 0;

    for (int i = 0; i < P.length; i++) {
      if (P[i]) {
        result++;
      }
    }
    result += calculateRow(P);

    return (result >= 0 && result < MAX_RESULT) ? result : MAX_RESULT;
  }


  private int calculateRow(boolean[] row) {
    int result = 0;

    boolean[] upperRow = new boolean[row.length - 1];

    for (int i = 0; i < row.length - 1; i++) {
      boolean product = row[i] || row[i + 1];
      upperRow[i] = product;
      if (product) {
        result++;
      }
    }

    if (result == 0) {
      return result;

    } else if (result == row.length - 1) {
      if (result > NODES_FOR_MAX_RESULT) {
        return MAX_RESULT;
      } else {
        return result + countAllNodesAbove(result);
      }

    } else {
      result += calculateRow(upperRow);

      if (result > MAX_RESULT) {
        return MAX_RESULT;
      }
    }

    return result;
  }

  private int countAllNodesAbove(int count) {
    if (count > NODES_FOR_MAX_RESULT) {
      return MAX_RESULT;
    } else {
      return (count)*(count - 1)/2;
    }
  }

}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.012 s

▶

example2
Second example test.

✔

0.008 s

Code: 18:45:54 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

public class Solution {

  private static int MAX_RESULT = 1_000_000_000;
  private static int NODES_FOR_MAX_RESULT = 44720;

  public int solution(boolean[] P) {
    int result = 0;

    for (int i = 0; i < P.length; i++) {
      if (P[i]) {
        result++;
      }
    }
    result += calculateRow(P);

    return (result >= 0 && result < MAX_RESULT) ? result : MAX_RESULT;
  }


  private int calculateRow(boolean[] row) {
    int result = 0;

    boolean[] upperRow = new boolean[row.length - 1];

    for (int i = 0; i < row.length - 1; i++) {
      boolean product = row[i] || row[i + 1];
      upperRow[i] = product;
      if (product) {
        result++;
      }
    }

    if (result == 0) {
      return result;

    } else if (result == row.length - 1) {
      if (result > NODES_FOR_MAX_RESULT) {
        return MAX_RESULT;
      } else {
        return result + countAllNodesAbove(result);
      }

    } else {
      result += calculateRow(upperRow);

      if (result > MAX_RESULT) {
        return MAX_RESULT;
      }
    }

    return result;
  }

  private int countAllNodesAbove(int count) {
    if (count > NODES_FOR_MAX_RESULT) {
      return MAX_RESULT;
    } else {
      return (count)*(count - 1)/2;
    }
  }

}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.004 s

▶

example2
Second example test.

✔

0.004 s

Code: 18:45:59 UTC, java, final, score: 90

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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

public class Solution {

  private static int MAX_RESULT = 1_000_000_000;
  private static int NODES_FOR_MAX_RESULT = 44720;

  public int solution(boolean[] P) {
    int result = 0;

    for (int i = 0; i < P.length; i++) {
      if (P[i]) {
        result++;
      }
    }
    result += calculateRow(P);

    return (result >= 0 && result < MAX_RESULT) ? result : MAX_RESULT;
  }


  private int calculateRow(boolean[] row) {
    int result = 0;

    boolean[] upperRow = new boolean[row.length - 1];

    for (int i = 0; i < row.length - 1; i++) {
      boolean product = row[i] || row[i + 1];
      upperRow[i] = product;
      if (product) {
        result++;
      }
    }

    if (result == 0) {
      return result;

    } else if (result == row.length - 1) {
      if (result > NODES_FOR_MAX_RESULT) {
        return MAX_RESULT;
      } else {
        return result + countAllNodesAbove(result);
      }

    } else {
      result += calculateRow(upperRow);

      if (result > MAX_RESULT) {
        return MAX_RESULT;
      }
    }

    return result;
  }

  private int countAllNodesAbove(int count) {
    if (count > NODES_FOR_MAX_RESULT) {
      return MAX_RESULT;
    } else {
      return (count)*(count - 1)/2;
    }
  }

}

Analysis summary

The following issues have been detected: timeout errors.

Analysis

Detected time complexity:

O(N)

expand all Example tests

▶

example1
First example test.

✔

0.004 s

▶

example2
Second example test.

✔

0.004 s

expand all Correctness tests

▶

small_tests
Small hand-written tests.

✔

0.004 s

0.008 s

0.004 s

0.008 s

▶

small_only_trues
Small tests, only True values.

✔

0.004 s

▶

small_only_falses
Small tests, only False values.

✔

0.004 s

▶

small_lonely_true
Small tests, no two neighbors True.

✔

0.004 s

▶

small_lonely_false
Small tests, no two neighbors False.

✔

0.008 s

0.004 s

0.008 s

▶

small_random_tests
Small random tests.

✔

0.004 s

expand all Performance tests

▶

big_only_trues
Big tests, only True values.

✔

0.080 s

0.096 s

0.108 s

▶

big_lonely_false
Big tests, no two neighbors False.

✔

0.084 s

0.096 s

0.128 s

▶

big_random_tests
Big random tests.

✘

TIMEOUT ERROR
running time: 0.68 sec., time limit: 0.26 sec.

0.684 s

TIMEOUT ERROR, running time: 0.68 sec., time limit: 0.26 sec.

0.484 s

TIMEOUT ERROR, running time: 0.48 sec., time limit: 0.26 sec.

0.080 s

0.076 s

▶

max_tests
Max tests.

✔

0.156 s

0.200 s