3
\$\begingroup\$

This Codility challenge is to take an array of integers representing lengths of line segments, and determine whether or not it is possible to choose three distinct segments to form a triangle. (The sum of the lengths of any two sides must exceed the length of the remaining side.) Assume that A contains at most one million ints.

Complexity requirements:

  • Expected worst-case time complexity is O(n log(n));
  • Expected worst-case space complexity is O(n), not counting the input array A itself.

This is my solution:

import java.util.Arrays;
class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 6
        int n = A.length;

        if (n>1000000000) return -1;

        Arrays.sort(A);
        int p=0;
        int q=p+1;
        int r=q+1;
        for (;r<n;p++,q++,r++){
            if(A[p]+A[q]>A[r] && A[q]+A[r]>A[p] &&  A[r]+A[p]>A[q])
               return 1;
        }
        return 0;
    }
}

I don't how to achieve 100% correctness. I get only 93%.

\$\endgroup\$
11
  • 2
    \$\begingroup\$ please include the basics of the problem from the link. i clicked the link, and it wanted me to do the test, this could be considered spam by some, trying to lure people to a site. \$\endgroup\$
    – Malachi
    Nov 5, 2013 at 17:26
  • \$\begingroup\$ @Malachi: Since it's not a blatant intent to spam, it shouldn't apply here. However, it would be useful to have a better reference to this problem (which the OP may have to provide). \$\endgroup\$
    – Jamal
    Nov 5, 2013 at 17:34
  • \$\begingroup\$ @Malachi: You may also suggest the tag wiki for this new tag. \$\endgroup\$
    – Jamal
    Nov 5, 2013 at 17:36
  • \$\begingroup\$ @Jamal I suggested a tag wiki for that, I wasn't sure what it was at first, I had to go to the main site first, I have never heard of that site until today, but I can see it becoming a thing here on code review. similar to other sites where you compete by writing code, etc. \$\endgroup\$
    – Malachi
    Nov 5, 2013 at 17:42
  • 1
    \$\begingroup\$ @Malachi: It is on SO, so it should be okay. \$\endgroup\$
    – Jamal
    Nov 5, 2013 at 17:43

2 Answers 2

3
\$\begingroup\$

As has been pointed out, you must do several things to ensure you get the maximum marks.

  1. Ensure that negative numbers are checked for.
  2. Handle the MAX_INT overflow issue which could arise.

    You know 4 + 5 > 7 is same as 5 > (7 - 4). Yes I know you are grinning ;)

    This suggested solution is correct for this.

These two individual points should allow you to achieve the maximum score. Now I would just like to quickly go over some theory behind why this solution works.

Time complexities

It seems people keep asking you to address the "consecutive elements". You have already done this through the use of Arrays.sort(). This Java sort algorithm is referred to as a "tuned Quicksort" ( See http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#sort(int[]) ).

The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance. Quicksort is well known for its O( n log n ) time complexity (excluding extreme cases).

After this you do a single iteration over the array, which is considered O(n). When we add the two time complexities together we are given O( 2n log n) where constants are considered insignificant for Big-O notation. So to clarify this simplifies down to O(n log n) which was the upper bound of the problem.

How sorting solves non-consecutive elements

Once the array is sorted it is true that only consecutive triples need to be considered.

Consider the following array: {1,2,6,6,8}

Whilst it may be true that (1, 6, 6) is triangular, and is non-consecutive. It can also be proven that if that value is triangular then any number which lies between the initial 1, and 6 will also be triangular.

From this we can see that in the sort array, for each non-consecutive triangular triples which exists there also exists an consecutive triple.

Simplification from sorting

The sort operation allows you to simplify you checks later, and decrease execution time. When checking for negative number, you only need check the lowest number in the triple, as if this is >= 0 it is given the follow values must be >= that initial value.

This mean you only need check one value for negativity, not three.

This can be extended further into the actual triangular checks. If it is true that the smallest two numbers in the triple are larger than the largest number when summed, then all three statements are true.

1) A[P] + A[Q] > A[R]

2) A[Q] + A[R] > A[P]

3) A[R] + A[P] > A[Q]

Remembering the algorithm change to this, so these would be evaluated as

A[P] > (A[R] - A[Q])

Because we can guarantee that A[P] < A[Q] < A[R] due to A being sorted, we only need perform the one check above.

\$\endgroup\$
9
  • \$\begingroup\$ cool. But I didn't know about the "It can also be proven [......] be triangular" part, can you provide a link? \$\endgroup\$ Nov 5, 2013 at 20:21
  • \$\begingroup\$ I said can be proven ;), I haven't found a link which in fact proves this as of yet. But if you consider a large set of numbers, and try extreme cases, you will see it holds. Unfortunately I never continued my Maths further, so I do not have the knowledge required to draw up a full Mathematical proof for you. \$\endgroup\$ Nov 5, 2013 at 20:25
  • \$\begingroup\$ Thank you! So I have to change the if with A[P]>(A[R]-A[Q]) in case the first number of triangle is negative! \$\endgroup\$
    – Thor
    Nov 6, 2013 at 10:22
  • \$\begingroup\$ @user31565 A[P]>(A[R]-A[Q]) is to prevent the problem of an overflow exception if A[P] + A[Q] > MAX_INT, for this problem you are required to ignore negative numbers as they are invalid. Which is why you first do a check of A[P] >= 0. \$\endgroup\$ Nov 6, 2013 at 10:42
  • 1
    \$\begingroup\$ Suppose there are some values P, Q, and R such that P < Q, Q < R, and A[P] > A[R] - A[Q]. Since R - 2 >= P and R - 2 >= Q, and since the array is sorted, it follows that A[R - 2] >= A[P] and A[R - 1] >= A[Q]. From that it follows that A[R - 2] > A[R] - A[R - 1]. In other words, if there are three entries anywhere in the array that can form a triangle, then there are three consecutive entries that can form a triangle. That's why it's sufficient to check only consecutive entries. \$\endgroup\$
    – David K
    Aug 16, 2014 at 17:35
2
\$\begingroup\$

Funny things that we(human) know that 2,147,483,647 + 1 = 2,147,483,648 but computer thinks otherwise. Ahhh! see, so now what to do?

You know 4 + 5 > 7 is same as 5 > (7 - 3). Yes I know you are grinning ;)

And also as 200_success suggested you are considering consecutive elements but problem definition say otherwise.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.