CareerCup

Hashing... Create a hash for all the elements in first pass and in second pass check for hash(sum-element) return on first occurrence. This needs extra space for hash table. time comp ll be O(n).

a straight forward way would be find the combination of any two elements in array and check their summation. It's O(n^2), I guess they want a O(nlogn) or better method? Anyone come up with better method?

a straight forward nlgn sol would be to sort the array (nlgn) and then for n numbers pick number one by one, subtract it from the input number N and search for the N-a[i] in the sorted list using binary search...

this wud require nlogn for sorting and then in worst case n times the searching time which is log n...so overall it wud be 2nlogn ~ O(nlogn)

Construct a new_array of same length. This is not very optimal solution as it need O(n) extra space.
While parsing array populate a new_array by "number" - array[i]. And before populating check for array[i] is in new_array or not.
for( i=0; i<len; i++)
{
if(i==0)
new_array[i]=number-array[i];
else
{
for(j=0;j<i;j++)
{
if(array[i]==new_array[j])
return found;
}
new_array[i]=number-array[i];
}
}

Construct a new_array of same length. This is not very optimal solution as it need O(n) extra space.
While parsing array populate a new_array by "number" - array[i]. And before populating check for array[i] is in new_array or not.
for( i=0; i<len; i++)
{
if(i==0)
new_array[i]=number-array[i];
else
{
for(j=0;j<i;j++)
{
if(array[i]==new_array[j])
return found;
}
new_array[i]=number-array[i];
}
}

Dump array values into a map (C++) inserting the array values as keys and the array indexes as values. A map only takes one unique key for each value so this eliminates the latter occurrences of the same number which is good.

Subtract the total e.g. 17 - a[i] which is 17 - 5 = 12. We then try to find if there is a 12 in the map then i++ etc.. this code should work

int index1;
int index2;
void addSequence( int num)
{
    int a[] = {5,10,3,8,9,7};
    map<int, int> seq_map;
    map<int,int>::iterator it;

    for(int i=0;i<sizeof(a)/sizeof(int);i++)
    {
        seq_map.insert(pair<int,int>(a[i],i));
        
    }
     for(int i=0;i<sizeof(a)/sizeof(int)-1;i++)
     {
         int temp = num - a[i];
         it = seq_map.find(temp);
         if(it->first == temp)
         {
             index1 = i;
             index2 = seq_map.find(temp)->second;
             break;
         }
     }
}
int main()
{
    int total = 17;
    addSequence( total);
    cout<<"index1 = "<<index1<<"  Index2 = "<<index2<<endl;
    return (0);
}

List<int> FindNumbers(List<int> numbers, int key)
        {
            List<int> ans = new List<int>();
            Dictionary<int,bool> seenNumbers = new Dictionary<int,bool>();
            foreach (int n in numbers)
            {
                if (seenNumbers.ContainsKey(key - n))
                {
                    ans.Add(n);
                    ans.Add(key-n);
                    break;
                }
            }
            return ans;
        }

import java.util.Hashtable;

public class ArrayNumberSum {

public static void main(String[] args) {
int magicNumber = 16;
int[] intArray = new int[] { 1, 12, 10, 4, 5, 7 };
int[] result = calculate(intArray, magicNumber);

System.out.println("Two values that add up to " + magicNumber + " are " + result[0] + " and " + result[1] + ".");

}

/**
* Ideally to solve this problem, we will create a hashtable that keep as Key the array[i] and the value
* the difference between the array[i] and the magicNumber.
*
* Once the difference is equal to a key, it means we found the two numbers.
*/
static int[] calculate(int[] n, int magicNumber) {
int[] result = new int[2];
Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();

for (int i = 0; i < n.length; i++) {
int diff = magicNumber - n[i];
int key = n[i];

if (!table.containsKey(key) // just to perform better
) {
table.put(key, diff);

// check if one key is equal to my difference values
if (table.containsKey(diff)) {
result[0] = diff;
result[1] = key;
break;
}
}
}

return result;
}
}

import java.util.Hashtable;

public class ArrayNumberSum {

    /**
     * PROBLEM: Find two numbers in an array that sum to a magic number value
     */
    public static void main(String[] args) {
        int magicNumber = 16;
        int[] intArray = new int[] { 1, 12, 10, 4, 5, 7 };
        int[] result = calculate(intArray, magicNumber);

        System.out.println("Two values that add up to " + magicNumber + " are " + result[0] + " and " + result[1] + ".");

    }

    /**
     * Ideally to solve this problem, we will create a hashtable that keep as Key the array[i] and the value
     * the difference between the array[i] and the magicNumber.
     * 
     * Once the difference is equal to a key, it means we found the two numbers.
     */
    static int[] calculate(int[] n, int magicNumber) {
        int[] result = new int[2];
        Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();

        for (int i = 0; i < n.length; i++) {
            int diff = magicNumber - n[i];
            int key = n[i];

            if (!table.containsKey(key) // just to perform better
            ) {
                table.put(key, diff);

                // check if one key is equal to my difference values
                if (table.containsKey(diff)) {
                    result[0] = diff;
                    result[1] = key;
                    break;
                }
            }
        }

        return result;
    }
}

std::pair<int,int>
testArraySum(int aArray[], const int aSum,
const int aArrlength)
{
// iterator ctor
std::vector<int> w_tmp(aArray,aArray+aArrlength);
assert(w_tmp.size()==aArrlength); // sanity check
std::vector<int>::const_iterator vbeg = w_tmp.begin();
std::vector<int>::const_iterator cvbeg= w_tmp.begin();
std::vector<int>::const_iterator cvend = w_tmp.end();
while( cvbeg!=cvend) // traverse container
{
vbeg=cvbeg+1; // next in the list
while(vbeg!=cvend) // sum 2-adjacent number
{
// do the sum
std::vector<int>::value_type w_sum = *cvbeg+*vbeg;
if( w_sum==aSum)
{
return std::make_pair(*cvbeg,*vbeg);
}
++vbeg;
}
++cvbeg; //
}
return std::make_pair(0,0); // default
}

bool first_sum(vector<int>& arr, int start, int end, int sum)
{
for (int i = start; i < end-1; i++)
{
for (int j = i+1; j < end; j++)
{
if(arr[i]+arr[j] == sum)
{
bool first = first_sum(arr,i+1,j,sum);
if(!first)
cout<<arr[i]<<"+"<<arr[j];
return true;
}
}
}
return false;
}

Might sound a lil too complex but bear with me.

1. Sort (nLog-n)
2. i -> 0 to n
key = sum - a[i]
The key is the hint to the position of the second number.
if key ~= sum
Start search on far right of 'i' // sorted small to big
key ~= 0
Start search on far left of 'i'
key ~= sum / 2
Search numbers near the i

How do you define first 2 elements? if the 1st element and 10th element for the sum and if the 2nd and 8th form the sum which one should we choose?