CareerCup

My algorithm is a slight tweak of the algorithm which finds all pairs that sum up to certain value. Algorithm sorts the array first and initialize first = 0, last = last element. Then iteratively it examines the array. Here is the code:

def findPairsLessThen(a, s):
	if len(a) < 2:
		return None
	a.sort()
	first = 0
	last = len(a) -1
	while first < last:
		if a[first] + a[last] > s:
			last -= 1
		else:
			for i in range(first + 1, last + 1):
				print a[first] + a[i], first, i
			first += 1

Approach:
1). QuickSort the list
2). Find out the max position (say p) where it's just less than or equal to K
3). Loop through the list starting at (P) backward. Find the difference between the current indexed number and K (say q). Use binary search to find the max (say t) position of q. Then combine everything below t and p to add to the answer set.

Sample data:
List: 1, 3, 5, 9, 20, 28, 30, 37, 60, 100
K: 50

So, the max position of p is at 37. Now, we loop through the list backward, 37 +30 <= 50? No. 37 + 28 <= 50? No. 37 + 20 <= 50? No. 37 + 9 <= 50? Yes. Then combine everything below 9 and 37.

pseudo code:

quicksort(list)

int p = binarysearch_max_position(k, list.length)
// p is the max position where it's just less than or equal to k in the list

for (i=p; i>=0; i--) [

x = list(i);

d = k - x;
// d is the difference in between k and x

j = binarysearch_max_position_helper(d,i)
// find the max position where j can exist
// since everything below j is less than j
// that it means position [0 to j] can be
// added to x and still be less than or equal
// to k

(if j != -1) {
all_combination_generator(j,i);
}

}

private void all_combination_generator(int i, int j) {

for (int x = i; x>=0; x--) {
answerset.add(j,list[x]);

}
}

Is this o(nlogn)?

1) Scan all elements and store all elements <= k in an array A O(n)
2) Sort this array. Let the total elements be e O(e*loge) in descending order
3) For i from 1 to e/2
d = k-A[i]
Do a binary search in this array to find the position of d. Output pairs A[i] and all A[j<=d]

Total complexity O(n) + O(e*loge)

You mean it is a list? If it is a list, you can't quicksort it, don't you? Only mergesort may apply. But still it is not random access. So if it is a list, either use map(this will be O(n),O(n)) or use loop(O(n^2),O(1))

how about a modified version of a count sort where n is the number of records, and a is the array, if we assume that 0 <= a[0:n] <= m, we allocate a new array b of size m that stores the sorted array, and a Hash Set of capacity m that stores an ADT called Solution,

The Solution ADT is a pair of integers, a and b, the idea is that a + b <= k, and more solutions can be from the fact that all Solution(a, 0...b) and Solution(0...b) are also solutions

At the end we will have a Set of Solutions

pseudocode:

for i in 0...n {
   b[a[i]] += 1;
   if(b[a[i]]) > 0 {
      solutions.add(new Solution(b[a[i]], k - b[a[i]]));
   }
}

solutions = expandSolutions(solutions);

space complexity would be O(2m)

time complexity would be O(n + expandSolutions) = O(n + k^2)


if k is <<< n then the whole thing could run in O(n)

Will you let me know what exactly the array j is containing.. and what are you trying to decrease with j--?

I think it can be done in O(n^2)

Iterate through the array and keep on creating the set with that number in case its lesser than k and also check that number against all the existing sets to see if that satisfies the criteria.

Can we use hashmap here?
like we can scan the list for numbers less than or equal to k and store it in hashmap (n, k-n). After putting all the elements we can just scan through the hash map and for each key, we will just have to check if the value is present in the key set. If yes then consider that to be the pair and continue with other keys.

#include<iostream>
#include<algorithm>

using namespace std;

int main()
{

int a[] = {3, 1, 4, 2, 9, 10, 33, 42, 2, 0, 6};
int N = sizeof(a) / sizeof(*a);
sort(a, a + N);
for(int x=0 ;x<N;x++)
{

cout<< a[x]<<" , ";
}
cout<<endl;


int K = 12;
int i = 0;
int *t = std::upper_bound(a, a + N, K - a[0]);
int j = t-a-1;
cout<< *t << " "<< *a<<" "<<j<<" "<<endl;

while (i < j) {
for (int k = i + 1; k <= j; k++)
cout << "(" << a[i] << ", " <<a[k] << ") ";
i++;
while (a[i] + a[j] > K && i < j) {
j--;
}
}system("pause"); }

I would approach it that way:

1. Sort the list in ascending order with nLogn (e.g. QuickSort)
2. Allocate two indexes––smaller and bigger (at the beginning smaller points to the first element of the list and bigger points at the last element)
3. Make a while loop with a termination condition smaller != bigger. Now compute the sum list(smaller)+list(bigger). If it is greater than k, there's no need to find the sums of the rest elements with bigger, so decrement bigger by 1 and continue to the beginning of the loop.

Else if the sum is smaller or equal to k, print out smaller paired with each of the rest of the elements. Increment smaller by 1 and continue to the beginning of the loop.

I have a simple solution in O(nlogn). First sort the list of numbers. Then iterating from starting (i=1 to n). Do a modified binary search for the remaining n-i+1 elements with l=i ,r=n and find the element of index with floor (k-a[i]). No_of_pairs+= g-i+1.

Please comment if there's any error with the logic.

Solution with time O(n) and space O(k)

Make an array arr[k]
Scan the list and increment index at position arr[i]
Have a pointer i = a[0] and j = a[k]
Find min(a[i], a[j])
Increment i and decrement j.

Why do we need O(n^2log(n)) to solve this ??

Even the brute force solution, where we simply produce all the pairs and check if their sum is <k or not is O(n^2)

I don't believe that we can solve this problem in anything less than O(n^2) because in worst case sum of elements for all the pairs will be <k and there are O(n^2) pairs.

int a[] = {3, 1, 4, 2, 9, 10, 33, 42, 2, 0, 6};
    int N = sizeof(a) / sizeof(*a);
    
    sort(a, a + N);
    int K = 12;
    int i = 0;
    int *t = std::upper_bound(a, a + N, K - a[0]);
    int j = t - a - 1;

    while (i < j) {
        for (int k = i + 1; k <= j; k++) 
            cout << "(" << a[i] << ", " <<a[k] << ") ";
        i++;
        while (a[i] + a[j] > K && i < j) {
            j--;
        }
    }

My algorithm is as follows:
First of all, I assume the integers in the array and K are nonnegative numbers.
I use a hash table to store numbers as a key and the count of that number as a value.

PseudoCode

for(Integer i : arr) {
	for(int j=K-i; K>=i &&  j>=0; j--) {
		if(HashMap.containsKey(j))
			sum += HashMap.get(j); // You can print out the pairs here. (i, j) which sums less than or equal to K. and its number is HashMap.get(j) for one i.
	}
	if(HashMap.containsKey(i))
		HashMap.put(i, HashMap.get(i)+1);
	else HashMap.put(i, 1);
}

From the two loops, I think the complexity is O(n * K).

1) Sort the list first.
2) Using binary search find last number which is not bigger then k. Lets say this number is located at position 'p'.
3) Create to pointer which initially are at the following positions:
- start = 0
- end = p
4) Check following conditions:
pseudo code:

while (start < end) {
	int sum = arr[start] + arr[end]; 
	if(sum == k) {
		print arr[start], arr[end];
		start++;
		end--;
	} else if (sum > k) {
		end--;
	} else {
        print arr[start], arr[end];
		start++;
	}
}

O(nlogn)