Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Problem: Given a array of distinct integers, how many triple integers sum to exactly zero
//
// ComputationalGeometry.swift//
// Created by James Rochabrun on 5/2/17.
//
//
import Foundation
//types of algorhitms
//1) constant -> 1 (1)
// a = b + c
//2) logarithmic -> log N (~1)
//bynary search
//3) linear -> N (2)
//loop
//4) linearithmic -> N log N (~2)
//mergesort
//5) quadratic -> N^2 (4)
//double loop
//6) cubic -> n^3 (8)
//triple loop
//7) exponential -> 2^N T(N)
//exhaustive search
//Binary search algorithm : logarithmic
//brut algorithm three sum problem
//Problem: Given a array of distinct integers, how many triple integers sum to exactly zero
let integers = [-50,-40, 10, 30, 40, 50, -20, -10, 0, 5]
//Step 1 sort Array
let sortedArray = integers.sorted()
//(n ^ 3) cubic solution
func findTripleSumEqualZero(in integers: [Int]) -> Int {
let n = integers.count
var count = 0
var a = 0
var b = 0
var c = 0
for i in 0..<n {
a += 1
for j in (i + 1)..<n {
b += 1
for k in (j + 1)..<n {
c += 1
if integers[i] + integers[j] + integers[k] == 0 {
count += 1
print("[\(integers[i]),\(integers[j]),\(integers[k])]")
}
}
}
}
// print(a,b,c)
return count
}
print("brutCount:", findTripleSumEqualZero(in: sortedArray))
//implementing a binary search - log N
func find(value: Int, in array: [Int]) -> Int {
var leftIndex = 0
var rightIndex = array.count - 1
while leftIndex <= rightIndex {
let middleIndex = (leftIndex + rightIndex) / 2
let middleValue = array[middleIndex]
if middleValue == value {
return middleIndex
}
if value < middleValue {
rightIndex = middleIndex - 1
}
if value > middleValue {
leftIndex = middleIndex + 1
}
}
return 0
}
//refactoring the three sum problem in to N^2 log N
func findTripleSumEqualZeroBinary(in integers: [Int]) -> Int {
let n = integers.count
var count = 0
//loop the array twice N^2
for i in 0..<n {
for j in (i + 1)..<n {
//Sum the first pair and assign it as a negative value
let twoSum = -(integers[i] + integers[j])
// perform a binary search log N
// it will return the index of the give number, this replaces the third loop
let index = find(value: twoSum, in: integers)
//to avoid duplications we need to do this check by checking the items at correspondingly indexes
if (integers[i] < integers[j] && integers[j] < integers[index]) {
print("\([integers[i], integers[j], integers[index]])")
count += 1
}
}
}
return count
}
print("count:", findTripleSumEqualZeroBinary(in: sortedArray))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment