Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
if tsum corresponds to more than 3 pairs, this won't work, will it? How about putting all the (x, y) that has same num[x]+num[y] into a vector:
map<int, vector<Node>> hashmap;
then
auto iter:hashmap
if(iter.second.size() >=2)
{
//output all the valid quadruple
}
I can only think out two algorithms.
First one is sorting array and traversing the array like 3-sum problem;
Second one is using hashing to record pair sums.
The first one's time complexity is O(n^3) and the second one's time complexity is O(n^2). Could anyone share a O(n^2) complexity at most with sorting? Thanks.
how do you get 2nd with O(n^2)? Correct me if I am wrong.
Computing sum of pair is O(n^2), find out two pair with different indices in one element in set is O(n^3) because the length of pairs is O(n^2) and finding out pairs with different indices in O(n^2) is at least O(n), right?
public static void printVal(int[] arr) {
if (arr.length == 0 || arr.length < 4) return;
HashMap<Integer, ArrayList<Pair>> map = new HashMap<Integer, ArrayList<Pair>>();
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
Pair p = new Pair(i,j);
if (map.containsKey(arr[i] + arr[j])) {
map.get(arr[i] + arr[j]).add(p);
} else {
ArrayList<Pair> arrList = new ArrayList<Pair>();
arrList.add(p);
map.put(arr[i] + arr[j], arrList);
}
}
}
for (Integer i : map.keySet()) {
ArrayList<Pair> list = map.get(i);
if (list.size() == 2) {
System.out.println(list.get(0).one + " " + list.get(0).two + " " +
list.get(1).one + " " + list.get(1).two);
}
if (list.size() > 2) {
for (int k = 0; k < list.size() - 1; k++) {
for (int m = k + 1; m < list.size(); m++) {
System.out.println(list.get(k).one + " " + list.get(k).two
+ " " + list.get(m).one + " " + list.get(m).two);
}
}
}
}
}
public class Pair {
int one;
int two;
public Pair(int o, int t) {
one = o;
two = t;
}
}
What I think that is important about this problem and a way to reduce the O() is that A + B = C + D is also the same as B + A = D + C and it should be checked again. What we can do is get all the possible combinations of 2 digits within that array and save the result. Such an operation will take O ( n!/2*(n-2)! ) and is basically the formula to calculate the possible combinations between k elements (in this case 2) in a list of n elements
Here is my code in PHP to print all the possible combinations:
$list = array(3,4,7,1,2,9,8);
$results = array();
for ($i=0; $i<count($list); $i++) {
for ($j=$i+1; $j<count($list); $j++) {
$sum = $list[$i] + $list[$j];
if (isset($results[$sum])) {
//we have a match
foreach ($results[$sum] as $pair) {
echo $pair[0].",".$pair[1].",".$i.",".$j."<br/>";
}
}
$results[$sum][] = array($i,$j);
}
}
I can think of the below
1. Have 2 windows; and keep them 2 digits apart
2. Each window has 2 pointers; max, Min, and variable: Sum as sum btw max, min pointers
3. get sum of left window and right; if they are same print it out
4. Slide the windows by a digit to right.
5. On slide we know the old index of min; subtract the value from the Sum; we konw the new index of max so add that value to the Sum
the complexity should be o(n)
Assuming array elements will traversed from Left to Right...like a..b.c..d..
and Minimum size of array should be 4...
so
#define LHS (A,B) A+B
#define RHS (C,D) C+B
....in a loop..
for ( int i=0; i <n-4;++i)
for ( int j=i+1;j<n-3;++j)
for ( int k=j+1;k<n-2;++k)
for (int l=k+1;k<n-1;++l)
{
if ( LHS(a[i],a[j]) == RHS(a[k][a[l])
cout<<i<<j<<k<<l<<"Are the indexes" <<endl;
i=j=k=l=n;
}
....
in case if the array element traverse any order..need to execute one more function in reverse order..
I think a general solution will b of the complexity O(n^3).
1. Make a structure like
struct ds
{
int value;
int index;
};
2. Sort according to values. // This process is nlogn
3. Iterate trough all pair (A,B) // This process is O(n^2)
a).compute sum = A+B
b).search two indexes(i,j) in sorted array such that :
Array[i]+array[j]=sum // ths process is O(n) in sorted array
So complexity is O(n^3).
This can be improved using hashing.
C#
int[] ar = { 3, 4, 7, 1, 2, 9, 8 };
for (int i=0; i<6;i++)
for (int j = 1; j < 6; j++)
for (int k = 2; k < 6; k++)
for (int p = 3; p < 6; p++)
{
int[] s = { ar[i], ar[j], ar[k], ar[p] };
if (s.Distinct().Count() == 4)
{
if (ar[i] + ar[j] == ar[k] + ar[p])
{
Console.WriteLine(ar[i] + "," + ar[j] + "," + ar[k] + "," + ar[p]);
}
}
}
Console.Read();
can it be not done like this
assuming you have array of n
array[n] = 1,2,3,4,....n
take a two dimensional array (could be optimized)\
sum[n][n-1] = {
array[0]+array[1], array[0]+array[2], ..array[0]+array[n-1],
array[1]+array[2],array[1]+array[3],...array[1]+array[n-1],
.
.
array[n-2]+array[n-1]
}
this operation will take O(n^2 )
now search for equal values in
sum[0][] with sum[1][] to sum[n-1][]
similarly for
sum[1][] with sum[2][] to sum[n-1][]
till
sum[n-3][] with sum[n-2][]
this is again O(n^2)
so total complexity should be max 2(n^2)
my java approach
public static void printSumPairs(int[] a){
HashMap<Integer,List<Point>> map = new HashMap<Integer,List<Point>> ();
List<Point> list;
for(int i=0; i< a.length; i++){
for(int j=i+1; j<a.length; j++){
list = map.get(a[i]+a[j]);
if(list==null){
list = new ArrayList<Point>();
}
list.add(new Point(i,j));
map.put(a[i]+a[j],list);
}
}
for (Integer key : map.keySet()) {
list = map.get(key);
if(list.size()>1){
for(int i=0; i< list.size()-1; i++)
{
if(list.get(i).x!=list.get(i+1).x && list.get(i).y!=list.get(i+1).y
&& list.get(i).x!=list.get(i+1).y
&& list.get(i).y!=list.get(i+1).x){
System.out.println(a[list.get(i).x]+"+"+a[list.get(i).y]+" = " +
a[list.get(i+1).x]+"+"+a[list.get(i+1).y]);
}
}
}
}
}
}
class Point{
int x;
int y;
Point(int a, int b){
x=a;
y=b;
}
O(n^2) using hash tables.
C++:
#include <unordered_map>
#include <set>
#include <vector>
#include <iostream>
typedef std::vector<int> IntVector;
typedef std::pair<int, int> IntPair;
typedef std::set<IntPair> PairSet;
typedef std::unordered_map<int, PairSet> SumMap;
void twoPairsSum()
{
int ar[] = {3, 4, 7, 1, 2, 9, 8};
SumMap map;
int i, j;
for (i = 0; i < 7; ++i) {
for (j = i+1; j < 7; ++j) {
int sum = ar[i] + ar[j];
map[sum].insert(IntPair(i, j));
}
}
// Find pairs
for (const auto &mit: map) {
const PairSet &set = mit.second;
PairSet::const_iterator sit, send;
PairSet::const_iterator sit2;
for (sit = set.begin(), send = set.end(); sit != send; ++sit) {
for (sit2 = ++PairSet::const_iterator(sit); sit2 != send; ++sit2) {
int A = sit->first;
int B = sit->second;
int C = sit2->first;
int D = sit2->second;
if (A != C and B != D) {
std::cout << "(" << A << ", "
<< B << ", " << C
<< ", " << D << ")\n";
return;
}
}
}
}
}
and
// Time complexity : O(n^2) - traversing every pair of indexes in the array
// Memory complexity : O(n^2) - every pair is stored in the hashtable in the worst case
void ABCD(int * arr, int n, int & a, int & b, int & c, int & d)
{
// a hash table to store sum values : SUM -> (i, j)
unordered_map<int, pair<int, int> > sum;
for (int i=0; i<n; i++)
{
for (int j=i+1; j<n; j++)
{
int s2 = arr[i] + arr[j];
// if the current sum was previously found we are done
if (sum.find(s2) != sum.end())
{
// the 2 indexes from the hash table
a = sum[s2].first;
b = sum[s2].second;
// the current indexes
c = i;
d = j;
// done
return;
}
// if the current sum wasn't previously found, HASH IT
// SUM -> (i, j)
else
sum[s2] = pair<int, int>(i,j);
}
}
}
and
There are two ways this can be solved:
1 - use 4-depth loops to iterate through all combinations of pairs. This is O(1) of size but O(n^4) of time
2 - use hashtable of lists of pairs to cache all sums as they are met and use 2-depth loops to find out all pairs of numbers. Then for each sum print out all pairs permutations.
This uses O(n^2) of size but O(n^2) of time. Actually this reduces to 2n^2 in case all numbers are equal but this it's O(n) complexity is not changed though
1. Sort the Array
2. Take two pointers left (start of the array) and right (end of the array)
3. Find the sum of the left and right value in the array
4. Look up iteratively the sum within the subarray , if sum is found print it
4.a if sum is greater value then increment left side ( i ) or else reduce the (j) value
public static void indexSumPair(int arr[])
{
//Return the array if Size less than 4
if(arr.length < 4)
{ return; }
// Sort the array
Arrays.sort(arr);
// Take two pointer left and right
int left =0;
int right = arr.length-1;
// decrease the right pointer on each pass * array is sorted
for(;left<right;right--)
{
// Take sum of left and right
int outSum = arr[left] + arr[right];
int i = left;
int j = right -1;
// Apply Logic of Pairs in Array of Integers whose Sum is equal to a given Number
// look up the sum within the subarray
while(i<j)
{
if( arr[i]+arr[j] == outSum)
{
System.out.println( " ("+arr[i]+" , "+arr[j]+ ") = "+" ("+arr[left]+" , "+arr[right]+")" );
i++;
j--;
}
//
else if( arr[i]+arr[j] < outSum)
{
i++;
}
else if( arr[i]+arr[j] > outSum)
{
j--;
}
}
}
1. Sort the Array
2. Take two pointers left (start of the array) and right (end of the array)
3. Find the sum of the left and right value in the array
4. Look up iteratively the sum within the subarray , if sum is found print it
4.a if sum is greater value then increment left side ( i ) or else reduce the (j) value
-- This solution do not use any extra space , no HashMap
public static void indexSumPair(int arr[])
{
//Return the array if Size less than 4
if(arr.length < 4)
{ return; }
// Sort the array
Arrays.sort(arr);
// Take two pointer left and right
int left =0;
int right = arr.length-1;
// decrease the right pointer on each pass * array is sorted
for(;left<right;right--)
{
// Take sum of left and right
int outSum = arr[left] + arr[right];
int i = left;
int j = right -1;
// Apply Logic of Pairs in Array of Integers whose Sum is equal to a given Number
// look up the sum within the subarray
while(i<j)
{
if( arr[i]+arr[j] == outSum)
{
System.out.println( " ("+arr[i]+" , "+arr[j]+ ") = "+" ("+arr[left]+" , "+arr[right]+")" );
i++;
j--;
}
//
else if( arr[i]+arr[j] < outSum)
{
i++;
}
else if( arr[i]+arr[j] > outSum)
{
j--;
}
}
}
bankertapan, are you the author? Very good solution, I just could not find how to inject the "find all integers that sum to X" problem solution here, but everything is pretty simple :). Good O(n^2) solution with O(1) extra space
this will work only for quadruples that include arr[0], this will fail in a test like 2,4,1, 600,4
I don't think the code above is completely correct according to the question. It says "Find the index", not the values. So if you sort the array first, how would you know which index based on the code above?
The code above prints:
(2 , 8) = (1 , 9)
(3 , 7) = (1 , 9)
(2 , 7) = (1 , 8)
(2 , 3) = (1 , 4)
So one solution would be to have another array that is not modified, and lookup the index for each printed value.
The code provided can not deal with cases like: 0 1 4 5 8 10
since it only consider the result including the smallest number.
the above code is wrong.. The following input
new int[] {1,2,3,4,5}
. The out put is
(2 , 4) = (1 , 5)
(2 , 3) = (1 , 4)
.
But there is one more result which is
(2, 5) = (3, 4)
Python solution using a dictionary and itertools.combinations
import itertools
def find_same_sums(integers):
sums = {}
for i, iv in enumerate(integers):
for j, jv in enumerate(integers):
if i == j:
continue
tup = (iv, jv) if iv <= jv else (jv, iv)
sums.setdefault(iv + jv, set()).add(tup)
for tups in sums.itervalues():
if len(tups) < 2:
continue
for combination in itertools.combinations(tups, 2):
yield combination
for same in find_same_sums([3,4,7,1,2,9,8]):
print same
def find_pairs_with_same_sums(list):
sums = {}
for i in range(len(list)):
for k in range(i+1, len(list)):
sums[i, k] = list[i] + list[k]
print 'Dictionary of sums:'
print sums
flipped = {}
for key, value in sums.iteritems():
if value not in flipped:
flipped[value] = [key]
else:
flipped[value].append(key)
print 'Flipped dictionary of sums'
print flipped
for key, value in flipped.iteritems():
if len(value) > 1:
for i in range(len(value)):
for k in range(i+1, len(value)):
print 'SUM = {key}'.format(key=key),
print value[i] + value[k]
list = [3,4,7,1,2,9,8]
find_pairs_with_same_sums(list)
Dictionary of sums:
{(0, 1): 7, (1, 2): 11, (2, 5): 16, (1, 3): 5, (4, 6): 10, (1, 5): 13, (4, 5): 11, (5, 6): 17, (1, 4): 6, (2, 4): 9, (0, 6): 11, (2, 6): 15, (0, 5): 12, (3, 6): 9, (0, 4): 5, (2, 3): 8, (1, 6): 12, (0, 3): 4, (3, 4): 3, (0, 2): 10, (3, 5): 10}
Flipped dictionary of sums
{3: [(3, 4)], 4: [(0, 3)], 5: [(1, 3), (0, 4)], 6: [(1, 4)], 7: [(0, 1)], 8: [(2, 3)], 9: [(2, 4), (3, 6)], 10: [(4, 6), (0, 2), (3, 5)], 11: [(1, 2), (4, 5), (0, 6)], 12: [(0, 5), (1, 6)], 13: [(1, 5)], 15: [(2, 6)], 16: [(2, 5)], 17: [(5, 6)]}
SUM = 5 (1, 3, 0, 4)
SUM = 9 (2, 4, 3, 6)
SUM = 10 (4, 6, 0, 2)
SUM = 10 (4, 6, 3, 5)
SUM = 10 (0, 2, 3, 5)
SUM = 11 (1, 2, 4, 5)
SUM = 11 (1, 2, 0, 6)
SUM = 11 (4, 5, 0, 6)
SUM = 12 (0, 5, 1, 6)
Sort the array.
For each interval (i,j), find m,n in the interval which have the same sum.
struct ValIndx{
int value;
int index;
ValIndx(int v, int i):value(v), index(i){}
};
static int ValIndxCompare(const ValIndx& v1, const ValIndx& v2){
return v1.value < v2.value;
}
vector<ValIndx> v;
void find(vector<int>& nums){
int len = (int)nums.size();
if(len == 0) return;
for(int i = 0; i < len; i ++){
ValIndx vi(nums[i],i);
v.push_back(vi);
}
sort(v.begin(), v.end(), ValIndxCompare);
for(int i = 0; i < len; i ++){
for(int j = i+1; j < len; j ++){
int sum = v[i].value + v[j].value;
int begin = i+1;
int end = j;
while(begin < end){
int part = v[begin].value + v[end].value;
if(part == sum){
cout << v[i].index << " " << v[j].index << " "
<< v[begin].index << " " << v[end].index << endl;
begin++;
end--;
}
if(part < sum){
begin++;
}
if(part > sum){
end--;
}
}
}
}
}
Here's an answer in Objective-C
It's actually much more verbose than the other answers and relies on creating a separate sum object. But I find it easier to dissect at least.
@interface SumOfIndexes : NSObject
@property int firstIndex;
@property int secondIndex;
@property int sum;
@end
@implementation SumOfIndexes
@end
@implementation Calculator
- (NSArray*)findIndexesOfNumbersThatCanBeAddedTogetherFrom:(NSArray*)inputArray
{
NSArray *sums = [self createSumsFromArray:inputArray];
NSArray *matchingSums = [self matchingSums:sums];
return [self arrayOfIndexFromSums:matchingSums];
}
- (NSArray*)createSumsFromArray:(NSArray*)inputArray
{
NSMutableArray *sums = [[NSMutableArray alloc]init];
for (int a = 0; a < inputArray.count; a++)
{
for (int b = a; b < inputArray.count; b++)
{
if (b != a)
{
SumOfIndexes *newSum = [[SumOfIndexes alloc]init];
newSum.firstIndex = a;
newSum.secondIndex = b;
newSum.sum = [inputArray[newSum.firstIndex]intValue] + [inputArray[newSum.secondIndex]intValue];
[sums addObject:newSum];
}
}
}
return sums;
}
- (NSArray*)matchingSums:(NSArray*)sums
{
NSArray *matchingSums = [[NSArray alloc]init];
for (SumOfIndexes *aSum in sums)
{
NSPredicate *matchingSumsPred = [NSPredicate predicateWithFormat:@"sum == %@", @(aSum.sum)];
NSArray *currentMatchingSums = [sums filteredArrayUsingPredicate:matchingSumsPred];
if (currentMatchingSums.count > 1)
{
matchingSums = currentMatchingSums;
break;
}
}
return matchingSums;
}
- (NSArray*)arrayOfIndexFromSums:(NSArray*)sums
{
NSMutableArray *indexes = [[NSMutableArray alloc]init];
for (SumOfIndexes *aSum in sums)
{
[indexes addObject:@(aSum.firstIndex)];
[indexes addObject:@(aSum.secondIndex)];
if (indexes.count >= 4)
{
break;
}
}
return indexes;
}
@end
Here is a python implementation:
def eq_sums(arr):
if not arr:
return None
a, b, c, d = None, None, None, None
hash = {}
for i, x in enumerate(arr):
for j, y in enumerate(arr[i:]):
_found = hash.get(x+y)
print _found
if _found and _found != "%s-%s" % (x, y):
a, b = i, j
c, d = int(_found.split('-')[0]), int(_found.split('-')[1])
break
else:
hash.update({x+y: "%s-%s" % (x, y) })
return a, b, c, d
x = eq_sums([3,4,7,1,2,9,8])
print x
This is still a O(n^2) solution
A slight variations to print all sums (A + B = C + D )
let sums = [ ((x, y) , x + y ) | x <- [3,4,7,1,2,9,8] , y <- [3,4,7,1,2,9,8] , x < y ]
let combinations = [ ( fst i , fst j ) | i <- m , j <- m , (snd i ) == (snd j) && (fst i) /= (fst j) ]
gives :
[((3,7),(1,9)),((3,7),(2,8)),((3,9),(4,8)),((3,8),(4,7)),((3,8),(2,9)),((4,7),(3,8)),((4,7),(2,9)),((4,8),(3,9)),((1,4),(2,3)),((1,9),(3,7)),((1,9),(2,8)),((1,8),(2,7)),((2,3),(1,4)),((2,7),(1,8)),((2,9),(3,8)),((2,9),(4,7)),((2,8),(3,7)),((2,8),(1,9))]
Removing repeated sums :
{{
let combinations = [ ( fst i , fst j ) | i <- m , j <- m , (snd i ) == (snd j) && (fst i) /= (fst j) && (fst (fst i)) > (fst (fst j)) ]
[((3,7),(1,9)),((3,7),(2,8)),((3,8),(2,9)),((4,7),(3,8)),((4,7),(2,9)),((4,8),(3,9)),((2,3),(1,4)),((2,7),(1,8)),((2,8),(1,9))]
}}}
In PHP:
function printPairs($arr){
$temp = array();
$lenght = count($arr);
for($i=0;$i<$lenght-1;$i++) {
$j = $lenght-1;
while($j>$i) {
$temp[$arr[$i]+$arr[$j]][] = array($i,$j);
$j--;
}
}
$l = count($temp);
for($i=0;$i<$l;$i++)
{
if(count($temp[$i]) > 2){
for($k=0;$k<count($temp[$i])-1;$k++) {
$j=count($temp[$i])-1;
while($j>$k) {
echo '('.implode(',', $temp[$i][$k]).','.implode(',', $temp[$i][$j]).')';
$j--;
}
}
} elseif(count($temp[$i]) == 2) {
echo '('.implode(',', $temp[$i][0]).','.implode(',',$temp[$i][1]).')';
}
}
}
JAVA:
No sorting. Time O(n^2). Space O(n)
public static void printAllABCD(int[] vals) {
int sum = 0;
HashMap<Integer, ArrayList<Integer>> sumMap = new HashMap<Integer, ArrayList<Integer>>();
ArrayList<Integer> tmp;
int[][] sums = new int[vals.length][vals.length];
//Store all possible sums and indexes of the elements that give the sum
for (int i = 0; i < vals.length - 1; i++) {
for (int j = i + 1; j < vals.length; j++) {
if (sumMap.containsKey(vals[i] + vals[j])) {
tmp = sumMap.get(vals[i] + vals[j]);
if (tmp.contains(j) || tmp.contains(i)) {
continue;
} else {
tmp.add(j);
tmp.add(i);
}
} else {
tmp = new ArrayList<Integer>();
tmp.add(j);
tmp.add(i);
sumMap.put(vals[i] + vals[j], tmp);
}
}
}
//Iterate over the stored sums and output combination of indexes
for (Integer i : sumMap.keySet()) {
tmp = sumMap.get(i);
if (tmp.size() == 4) {
System.out.println(tmp + " = " + i);
} else if (tmp.size() > 4) {
for (int k = 0; k < tmp.size() - 2;) {
for (int j = k + 2; j < tmp.size();) {
System.out.println("[" + tmp.get(k) + ", " + tmp.get(k + 1) + ", " + tmp.get(j) + ", " + tmp.get(j + 1) + "] = " + i);
j = j + 2;
}
k = k + 2;
}
}
}
}
public static void findABEqualCDPoints(int[] values) {
Map<Integer, Index> sums = new HashMap<Integer, Index>();
for (int i=0; i<values.length; i++) {
for (int j=i+1; j<values.length; j++) {
int sum = values[i] + values[j];
if (sums.containsKey(sum)) {
Index point = sums.get(sum);
if (!point.isEqual(i, j) && point.indexOne < i && point.indexOne < j && point.indexTwo < i && point.indexTwo < j) {
System.out.println(sum);
System.out.println(point.indexOne + " " + point.indexTwo + " " + i + " " + j);
return;
}
} else {
sums.put(sum, new Index(i, j));
}
}
}
}
This solution actually maintains the correct keys in the array as the question states.
function findQuad(array $arr) {
asort($arr);
$keys = array_keys($arr);
$vals = array_values($arr);
$right = count($vals) - 1;
for ($left = 0; $left < $right; $right--) {
$sum = $vals[$left] + $vals[$right];
$i = $left;
$j = $right - 1;
while ($i < $j) {
$currSum = $vals[$i] + $vals[$j];
if ($currSum == $sum) {
echo $keys[$left] . ', ' . $keys[$right] . ', ' . $keys[$i] . ', ' . $keys[$j];
return;
} elseif ($currSum < $sum) {
$i++;
} else {
$j--;
}
}
}
}
echo implode(', ', $sample) . "\n";
findQuad($sample);
O(n^2)
import java.util.HashMap;
import java.util.Random;
public class Main {
private static Random rand = new Random();
//1
static public void main(String[] args){
int numTries = 10;
for(int i = 0; i < numTries; i++){
int n = Math.abs(rand.nextInt() % 20 + 5);
int[] input = new int[n];
for(int j = 0; j < n; j++){
input[j] = rand.nextInt() % 20;
}
solveEqn(input);
}
}
private static void solveEqn(int[] input){
HashMap<Integer, Indices> map = new HashMap<Integer, Indices>();
for(int i = 0; i < input.length - 1; i++){
for(int j = i + 1; j < input.length; j++){
int sum = input[i] + input[j];
Indices indices = map.get(sum);
if(indices != null){
if(indices.geti() != i && indices.getj() != j){
System.out.println(input[indices.geti()] + " + " + input[indices.getj()] + " = " + input[i] + " + " + input[j]);
return;
}
}
map.put(sum, new Indices(i, j));
}
}
System.out.println("No solution found.");
}
private static class Indices{
int i;
int j;
public Indices(int i, int j){
this.i = i;
this.j = j;
}
public int geti(){
return i;
}
public int getj(){
return j;
}
}
}
Here is the meat of the problem I'll let the consumer print the output to the console.
public static List<int> FindABEqualsCD(int[] A)
{
var memo = new Dictionary<int, List<int>>();
for(int i = 0; i < A.Length; i++)
{
for(int j = i + 1; j < A.Length, j++)
{
int t = A[i] + A[j]
if(!memo.ContainsKey(t))
{
memo.Add(t, new List<int>() { i, j };
}
else
{
memo[t].Add(i);
memo[t].Add(j);
return memo[t];
}
}
}
}
return null;
#include <unordered_map>
#include <vector>
using namespace std;
typedef pair<int, int> Pair;
vector<int> foursum(int in[], int len)
{
unordered_map<int, Pair> map;
vector<int> v;
for (int i = 0; i < len - 1; ++i)
{
for (int j = i + 1; j < len; ++j)
{
unordered_map<int, Pair>::iterator match = map.find(in[i] + in[j]);
if (match != map.end())
{
v.push_back(match->second.first);
v.push_back(match->second.second);
v.push_back(in[i]);
v.push_back(in[j]);
return v;
}
map[in[i] + in[j]] = Pair(in[i], in[j]);
}
}
return v;
}
public class findABEqualCDPoints {
public static void main(String args[]) {
int a[] = { 3, 4, 7, 1, 2, 9, 8 };
printSumPairsABCD(a);
}
public static void printSumPairsABCD(int[] a) {
HashMap<Integer, List<Index>> map = new HashMap<Integer, List<Index>>();
List<Index> list = new ArrayList<>();
for (int i = 0; i < a.length; i++) {
for (int j = i + 1; j < a.length; j++) {
Integer key = a[i] + a[j];
list = map.get(key);
if (list == null) {
list = new ArrayList<Index>();
list.add(new Index(i, j));
} else {
for (Index index : list) {
System.out.println(a[index.indexA] + " " + a[index.indexB] + " -- " + a[j] + " " + a[i]);
if (index.indexA != i && index.indexB != j && index.indexB != i && index.indexA != j) {
System.out.println(index.indexA + " " +
index.indexB + " -- " + j + " " + i);
}
}
list.add(new Index(i, j));
}
map.put(key, list);
}
}
}
static class Index {
int indexA;
int indexB;
Index(int indexA, int indexB) {
this.indexA = indexA;
this.indexB = indexB;
}
}
}
public static void print4Sum(int[] arr){
getSums(arr).values().forEach((x) -> printAllCombinations(x));
}
private static void printAllCombinations(List<Pair<Integer,Integer>> list){
for (int i = 0; i < list.size() - 1; i++){
Pair<Integer,Integer> p1 = list.get(i);
for (int j = i+1 ; j < list.size(); j++){
Pair<Integer,Integer> p2 = list.get(j);
System.out.printf("(%d,%d,%d,%d)\r\n",p1.getKey(),p1.getValue(),p2.getKey(),p2.getValue());
}
}
}
private static HashMap<Integer, List<Pair<Integer,Integer>>> getSums(int[] arr){
HashMap<Integer, List<Pair<Integer,Integer>>> result = new HashMap<Integer, List<Pair<Integer, Integer>>>();
if (arr.length < 4){
return result;
}
for (int i = 0 ; i < arr.length-1; i++){
if (i > 0 && arr[i] == arr[i-1]){
continue;
}
for (int j = i+1; j < arr.length; j++){
if (j > i + 1 && arr[j] == arr[j-1]){
continue;
}
int sum = arr[i] + arr[j];
List<Pair<Integer,Integer>> list;
if (!result.containsKey(sum)){
list = new ArrayList<>();
result.put(sum , list);
}
else{
list = result.get(sum);
}
list.add(new Pair<>(i, j));
}
}
return result;
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
public class SumOfTwoPairsInArray {
private static HashMap<Integer, ArrayList<Pair>> hm = new HashMap<Integer, ArrayList<Pair>>();
public static void checkIfTwoPairsHaveSameSum(int array[]) {
for(int i=0; i<array.length; i++) {
for(int j=i+1; j<array.length; j++) {
if(!hm.containsKey(array[i]+array[j])) {
ArrayList<Pair> arrayList = new ArrayList<Pair>();
arrayList.add(new Pair(i,j));
hm.put(array[i]+array[j], arrayList);
}
else {
hm.get(array[i]+array[j]).add(new Pair(i,j));
}
}
}
Iterator<Integer> itr = hm.keySet().iterator();
while(itr.hasNext()) {
Integer key = itr.next();
ArrayList<Pair> arrayList = hm.get(key);
if(arrayList.size() > 1) {
for(int i=0; i<arrayList.size(); i++) {
System.out.print("(" + arrayList.get(i).i + " , " + arrayList.get(i).j + " )");
}
System.out.println();
}
}
}
public static void main(String args[]) {
int array[] = {3,4,7,1,2,9,8};
checkIfTwoPairsHaveSameSum(array);
}
}
class Pair {
int i;
int j;
Pair(int i, int j) {
this.i = i;
this.j = j;
}
}
package arrays;
import java.util.HashMap;
public class FindSum {
public static void main(String[] args) {
System.out.println( "checking ");
int nums [] = {3,-4,7,1,2,-9,8};
HashMap <Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i =0; i < nums.length; i++)
map.put( nums[i], i);
for (int i =0; i< nums.length; i++){
int A= nums[i];
for (int j =i+1; j< nums.length -2 ; j++){
int B = nums[j];
int C = nums[j+1];
int D = A+B-C;
System.out.println("A+B-C = " + D );
System.out.println(" map contains? " + map.containsKey(D));
if(map.containsKey(D)){
int D_index = map.get(D) ;
System.out.println( "D_index from hashmap " + D_index);
System.out.println(i + "->"+nums[i]+ " ," +j + "->" +nums[j] + " ,"+
(j+1) + "->" +nums[j+1] +" ,"+map.get(D)+"->" + nums[+map.get(D)]);
}
}
}
}
}
Here is my answer with o(n^2) and use of Hash Map
The idea is A+B-C = D, loop through i & j, and check for D in hash map
package arrays;
import java.util.HashMap;
public class FindSum {
public static void main(String[] args) {
System.out.println( "checking ");
int nums [] = {3,-4,7,1,2,-9,8};
HashMap <Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i =0; i < nums.length; i++)
map.put( nums[i], i);
for (int i =0; i< nums.length; i++){
int A= nums[i];
for (int j =i+1; j< nums.length -2 ; j++){
int B = nums[j];
int C = nums[j+1];
int D = A+B-C;
System.out.println("A+B-C = " + D );
System.out.println(" map contains? " + map.containsKey(D));
if(map.containsKey(D)){
int D_index = map.get(D) ;
System.out.println( "D_index from hashmap " + D_index);
System.out.println(i + "->"+nums[i]+ " ," +j + "->" +nums[j] + " ,"+
(j+1) + "->" +nums[j+1] +" ,"+map.get(D)+"->" + nums[+map.get(D)]);
}
}
}
}
}
package arrays;
import java.util.HashMap;
public class FindSum {
public static void main(String[] args) {
System.out.println( "checking ");
int nums [] = {3,-4,7,1,2,-9,8};
HashMap <Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i =0; i < nums.length; i++)
map.put( nums[i], i);
for (int i =0; i< nums.length; i++){
int A= nums[i];
for (int j =i+1; j< nums.length -2 ; j++){
int B = nums[j];
int C = nums[j+1];
int D = A+B-C;
System.out.println("A+B-C = " + D );
System.out.println(" map contains? " + map.containsKey(D));
if(map.containsKey(D)){
int D_index = map.get(D) ;
System.out.println( "D_index from hashmap " + D_index);
System.out.println(i + "->"+nums[i]+ " ," +j + "->" +nums[j] + " ,"+
(j+1) + "->" +nums[j+1] +" ,"+map.get(D)+"->" + nums[+map.get(D)]);
}
}
}
}
}
import java.util.HashMap;
public class FindSum {
public static void main(String[] args) {
System.out.println( "checking ");
int nums [] = {3,-4,7,1,2,-9,8};
HashMap <Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i =0; i < nums.length; i++)
map.put( nums[i], i);
for (int i =0; i< nums.length; i++){
int A= nums[i];
for (int j =i+1; j< nums.length -2 ; j++){
int B = nums[j];
int C = nums[j+1];
int D = A+B-C;
System.out.println("A+B-C = " + D );
System.out.println(" map contains? " + map.containsKey(D));
if(map.containsKey(D)){
int D_index = map.get(D) ;
System.out.println( "D_index from hashmap " + D_index);
System.out.println(i + "->"+nums[i]+ " ," +j + "->" +nums[j] + " ,"+
(j+1) + "->" +nums[j+1] +" ,"+map.get(D)+"->" + nums[+map.get(D)]);
}
}
}
}
}
O(n^2) in java:
public static void main(String[] args) {
int[] arr = {3, 4, 7, 1, 2, 9, 8};
findFactors(arr);
}
static class Factors {
public Factors(int A, int B) {
this.A = A;
this.B = B;
}
int A;
int B;
}
public static void findFactors(int[] arr) {
Map<Integer, Factors> m = new HashMap<>();
int aux = 0;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
aux = arr[i] + arr[j];
if (m.containsKey(aux)) {
System.out.println(arr[i] + " + " + arr[j] + " = " + arr[m.get(aux).A] + " + " + arr[m.get(aux).B]);
System.out.println("(" + i + "," + j + "," + m.get(aux).A + "," + m.get(aux).B + ")");
} else {
m.put(aux, new Factors(i, j));
}
}
}
}
Output:
4 + 7 = 3 + 8
(1,2,0,6)
4 + 1 = 3 + 2
(1,3,0,4)
4 + 8 = 3 + 9
(1,6,0,5)
1 + 9 = 3 + 7
(3,5,0,2)
1 + 8 = 7 + 2
(3,6,2,4)
2 + 9 = 3 + 8
(4,5,0,6)
2 + 8 = 3 + 7
(4,6,0,2)
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int A[] = {3,4,7,1,2,9,8};
int N = sizeof(A)/sizeof(A[0]);
sort(A,A+N);
map<int,pair<int,int> > M;
vector<int> P;
for(int i=0;i<N-1;i++)
for(int j=i+1;j<N;j++)
{
int sum = A[i] + A[j];
if(M.find(sum) == M.end())
M.insert(make_pair(sum,make_pair(i,j)));
else
{
int C = M.find(sum)->second.first;
int D = M.find(sum)->second.second;
if(i != C && i != D && j != C && j != D)
cout<<A[i]<<" "<<A[j]<<" "<<A[C]<<" "<<A[D]<<endl;
}
}
return 0;
}
#include<iostream>
using namespace std;
bool isPairWiseSumEqual(int arr[], int start, int end)
{
for(int i=0;i<end;i++)
{
for(int j=i;j<=end;j++)
{
if(arr[i] > arr[j])
swap(arr[i], arr[j]);
}
}
if(arr[0]+arr[end] == arr[1]+arr[end-1])
{
cout<<arr[0]<<" + "<<arr[end]<<" = "<<arr[1]<<" + "<<arr[end-1]<<endl;
return true;
}
return false;
}
int i = 1;
void getFourNumbers(int arr[], int startA, int endA, int data[], int startD, int endD)
{
if(startA<=endA+1)
{
if(startD == endD+1)
{
int temp[endD+1];
for(int i=0;i<=endD;i++)
{
temp[i] = data[i];
}
bool check = isPairWiseSumEqual(temp, 0, endD);
i++;
return;
}
data[startD] = arr[startA];
getFourNumbers(arr, startA+1, endA, data, startD+1, endD);
getFourNumbers(arr, startA+1, endA, data, startD, endD);
}
}
void function(int arr[], int size)
{
int data[4];
getFourNumbers(arr, 0, size, data, 0, 3);
}
int main()
{
int arr[] = {3,4,7,1,2,9,8};
int size = sizeof(arr)/sizeof(*arr);
function(arr, size-1);
cout<<endl;
system("PAUSE");
return 0;
}
import java.util.*;
import java.util.Map.Entry;
public class ABCDArraySum {
static class Indices {
int x;
int y;
public Indices(int x, int y) {
this.x = x;
this.y = y;
}
}
static class Result {
Indices AB;
Indices CD;
int sum;
public Result(Indices AB, Indices CD, int sum) {
this.AB = AB;
this.CD = CD;
this.sum = sum;
}
}
public static void main(String[] args) {
Result res = getIndices(new int[] { 3, 4, 7, 1, 2, 9, 8 });
System.out.println("Sum Obtained: " + res.sum);
System.out.println("Indices: (" + res.AB.x + "," + res.AB.y + ")("
+ res.CD.x + "," + res.CD.y + ")");
}
private static Result getIndices(int[] arr) {
Result res = null;
Map<Integer, List<Indices>> resultMap = new HashMap<Integer, List<Indices>>();
int sum = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
sum = arr[i] + arr[j];
if (!resultMap.containsKey(sum)) {
resultMap.put(sum, new ArrayList<Indices>());
}
List<Indices> temp = resultMap.get(sum);
Indices ind = new Indices(i, j);
temp.add(temp.size(), ind);
}
}
Set<Entry<Integer, List<Indices>>> set = resultMap.entrySet();
Iterator<Entry<Integer, List<Indices>>> iter = set.iterator();
while (iter.hasNext()) {
Entry<Integer, List<Indices>> val = iter.next();
if (val.getValue().size() >= 2) {
res = new Result(val.getValue().get(0), val.getValue().get(1),
arr[val.getValue().get(0).x]
+ arr[val.getValue().get(0).y]);
break;
}
}
return res;
}
}
I use hash map to record the sum of two pair and find two pairs which has the same sum. Time is O(n^2)
- ronnie.alonso October 13, 2014