Find the combination of numbers making triangle [reviewed]
Problem
Find all triangle combination from a given array of integers.For example, given array of integers, {8,7,3,2,5,6,1,4}, your algorithm should produce list of combinations that makes triangle.
First of all, we should remember than given tree numbers, a, b, c, triangle can be made when
a + b > c (a < b < c)
If the input numbers are sorted in ascending order, we can easily the combination making triangle as below:
Figure 1. Initial algorithm |
1. Starting from the beginning of the array, choose for two numbers, a and b as shown in Figure 1.
1-1. Among the rest of numbers, find the third number, c satisfying a+b > c.
2. Shift a, b by one, perform the step 2 (see lower picture in Figure 1).
Let check the running time of this algorithm.
Sorting: O(NlogN)
Step 1: O(N2) (Loop takes O(N) and sub step 1-1 will take O(N) )
Overall: O(N2)
If we can optimize step 1-1 using binary search, which runs in O(log N). We can bring down the running time to O( N log N). The binary search algorithm would be similar to what we wrote in H-Inex problem. We just need to find the last position of c meeting c < a + b. (See Figure 2.)
Figure 2. O( N log N) with binary search |
Here is the complete code written in C++.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <vector> | |
#include <string> | |
#include <algorithm> | |
#include <iostream> | |
using namespace std; | |
bool compare(int prev, int next) | |
{ | |
return prev <= next; | |
} | |
int bsearch(vector<int>& list, int start, int end, int target, int last_pos) | |
{ | |
if (start> end) | |
return last_pos; | |
int h = start + (end - start) / 2; | |
if (list[h] >= target) | |
return bsearch(list, start, h - 1, target, last_pos); | |
last_pos = h; | |
return bsearch(list, h + 1, end, target, last_pos); | |
} | |
vector<vector<int>> find_triangle(vector<int> input) | |
{ | |
vector<vector<int>> result; | |
int a, b, c; | |
if (input.size() <3) | |
result; | |
sort(input.begin(), input.end(), compare); | |
for (a = 0, b = 1, c = 2; c < input.size(); c++) | |
{ | |
int target = input[a] + input[b]; | |
int found = bsearch(input, c, input.size() - 1, target, -1); | |
if (found != -1) | |
{ | |
for (int i = c; i <= found; i++) | |
{ | |
vector<int> found; | |
found.push_back(input[a]); | |
found.push_back(input[b]); | |
found.push_back(input[i]); | |
result.push_back(found); | |
} | |
} | |
a = b; | |
b = c; | |
} | |
return result; | |
} | |
int main() | |
{ | |
vector<int> input; | |
input.push_back(20); | |
input.push_back(3); | |
input.push_back(1); | |
input.push_back(4); | |
input.push_back(7); | |
input.push_back(15); | |
input.push_back(10); | |
input.push_back(9); | |
input.push_back(5); | |
vector<vector<int>> result = find_triangle(input); | |
for (int i = 0; i < result.size(); i++) | |
{ | |
for (int j = 0; j < result[i].size(); j++) | |
cout << result[i][j] << ","; | |
cout << endl; | |
} | |
return 1; | |
} |
Someone might say that the code will take O(N^2) because of the step iterative over the found numbers and add the results to the vector.
It is just for the testing, we can simply remember the start and end in the input array and print out the result later.
Practice statistics
8 mins: to think up the algorithm
16:10 mins: to write up the code
4:35 mins: to verify the code (no typo this time)
4:54 mins: to uncover the logical mistake (regarding how to store the results)
UPDATE(2019-07-26): solved the problem again. Came up with correct algorithm and complete the implementation on time. However, there was critical bug in the binary search code, which took more than 25 mins to find out after in-depth debugging.
Here is the solution in Python.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class FindTriangles: | |
def find(self, list): | |
self.result = [] | |
#sort in descending order | |
sorted_list = sorted(list, reverse=True) | |
for i in range(len(sorted_list)): | |
cpos = i | |
self.find_two_sides(sorted_list, i + 1, cpos) | |
return self.result | |
def find_two_sides(self, list, s, longest_pos): | |
longest = list[longest_pos] | |
for i in range(s, len(list)): | |
a = list[i] | |
last_side = longest - a | |
bpos = self.binary_search(list, i+1, len(list) - 1, last_side, None) | |
if bpos == None: | |
continue | |
for b in range(i+1, bpos + 1): | |
self.result.append([longest, a, list[b]]) | |
def binary_search(self, list, s, e, target, min_pos): | |
if s > e: | |
return min_pos | |
half = s + (e-s)//2 | |
if list[half] == target: | |
if half > s: | |
min_pos = half - 1 | |
return min_pos | |
elif list[half] > target: | |
if min_pos == None or min_pos < half: | |
min_pos = half | |
return self.binary_search(list, half + 1, e, target, min_pos) | |
else: | |
#list[half] < target | |
return self.binary_search(list, s, half - 1, target, min_pos) | |
input = [8,7,3,2,5,6,1,4] | |
finder = FindTriangles() | |
print ("input = {} output ={}".format(input, finder.find(input))) |
10:33.24: to come up with algorithm
15:08.58: to write the code
04:34.20: to review the code and fix syntax error
06:00: to fix the bug after running the code
18:28: to fix the bug in binary search.
Comments
Post a Comment