Triangle – Codility – Solution

Java solution to Codility Triangle problem (Lesson 6 – Sorting) which scored 100%. The problem is to determine whether a triangle can be built from a given set of edges. The strategy is to sort the array of integers and then check from the end if previous 2 elements have sum > current element.

[cc lang="java" escaped="true"]
package com.codility.lesson06.sorting;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Triangle {
    public int solution(int[] A) {
    	if(A.length < 3) return 0;
    	
		List aList = new ArrayList();
		for(int i=0; i<A.length; i++) { aList.add(A[i]); } Collections.sort(aList); //made long array because each int element can be as high as Integer.MAX_VALUE so when add them //can overflow int long [] aOrdered = new long[A.length]; int index = 0; for(Integer i : aList) { aOrdered[index++] = i; } //start from the end (largest) //if previous 2 elements have sum > current element, found a triangle 
		for(int i=aOrdered.length-1; i>=2; i--) {
			if(aOrdered[i-1] + aOrdered[i-2] > aOrdered[i]) {
				return 1;
			}
		}
    	return 0;
    }
}
[/cc]

TestNG test cases for this problem which all passed:

[cc lang="java" escaped="true"]
package test.com.codility.lesson06.sorting;

import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

import com.codility.lesson06.sorting.Triangle;

public class TriangleTests {
	private Triangle solution;
	
	@BeforeTest
	public void setUp() {
		solution = new Triangle();
	}

	@DataProvider(name = "test1")
	public Object [][] createData1() {
		return new Object [][] {
			new Object [] {  new int [] { 10, 2, 5, 1, 8, 20 }, 1 }, 
			new Object [] {  new int [] { 10, 50, 5, 1 }, 0 }, 
			new Object [] {  new int [] { 1 }, 0 },
			new Object [] {  new int [] { 1, 1 }, 0 },
			new Object [] {  new int [] { 1, 1, 1, 1 }, 1 }, //1 + 1 > 1
			new Object [] {  new int [] { -5, -3, -1, 2, 3, 5 }, 0 },
			new Object [] {  new int [] { -5, -3, -1, 2, 4, 5 }, 1 },
			new Object [] {  new int [] { Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE }, 1 },
			new Object [] {  new int [] { Integer.MAX_VALUE, Integer.MAX_VALUE-1, Integer.MAX_VALUE-1 }, 1 },
		};
	}

	@Test(dataProvider = "test1")
	public void verifySolution(int[] pA, int pExpected) {		
		Assert.assertEquals(solution.solution(pA), pExpected);
	}	
}
[/cc]