CareerCup

1. Insert all numbers from one of the list(say List1) to a HashTable/Map/Dictionary
2. Iterate through other List
a. n= target - list(i)
b. if hashTable.ContainsKey(n), then you found that pair

Complexity:
Space: O(n)
Time : since HashTable has constant time complexity in look up, it O(1)

If extra space is not allowed, then probably time complexity would be )(n2)

Sort both arrays, now get 2 pointers l2 and l1, one at the beginning of the second array and one at the end of the first array. For each iteration if l1+l2 > target then decrease l1, else increase l2, if l1+l2=target return l1 and l2, return false if l1 reaches the beginning of the first array and l2 reaches the end of the second array.

pulic int[] getSum(int[] list1 int[] list2, int target){

Arrays.sort(list1);
Arrays.sort(list2);

int l1 = list1.length-1;
int l2 = 0;

whiile(l1 >= 0 && l2 < list2.length){
	if(list1[l1] + list2[l2] == target){
		return [l1,l2];
	}else if(list1[l1] + list2[l2] > target){
		l1--;
	}else{
		l2++;
	}
}
return null;
}

Merge sort -in place(in-place Heap sort can be considered too O(nlogn) ) should do with binary search but yes time complexity will increase.
If API usage is allowed, why not use Arrays.sort function followed by binary search? But O(n log n) is not guaranteed as stated in the javadocs.

use sort or use hashing.

public static boolean istergetfound(int target ,ArrayList<Integer> list1,ArrayList<Integer> list2)
	{
		for(int i=0;i<list1.size();i++)
		{
			
			if(list1.get(i)>target)
				continue;
			int l1=list1.get(i);
			
			for(int j=0;j<list2.size();j++)
			{
			
			int l2=list2.get(j);
			if(l2+l1==target)
			{
				System.out.println("result found"+l1+"+"+l2+"="+target);
				return true;			}
			
			}
		}
	
	return false;
	}

The question can be solved with constant space and O(a+b) runtime, where a is the length of array1 and b is the length of array2, if the arrays are sorted

public class TwoArrSum {
  public static boolean sumExists(int target, int[] arr1, int[] arr2) {
    int pointer1 = 0;
    int pointer2 = arr2.length - 1;
    while (pointer1 <= arr1.length - 1 && pointer2 >= 0) {
      int sum = arr1[pointer1] + arr2[pointer2];
      if (sum < target) {
        pointer1++;
        if (pointer1 == arr1.length) {
          pointer1 = arr1.length - 1;
        }
      } else if (sum > target) {
        pointer2--;
        if (pointer2 == -1) {
          pointer2 = 0;
        }
      } else {
        return true;
      }
    }
    return false;
  }

  public static void main(String[] args) {
    int[] arr1 = {1, 3, 4, 7};
    int[] arr2 = {2, 4, 6, 8};
    int arg = Integer.parseInt(args[0]);
    System.out.println(sumExists(arg, arr1, arr2));
  }
}

The question can be solved with constant space and O(a+b) runtime, given that the arrays are sorted (a is the length of array1 and b is the length of array2). The idea is the start one pointer at the beginning of array1 and another at the end of array2. You increment pointer1 when the current sum is less than the target (thus increasing the sum) and decrement pointer2 if current sum is greater than the target (thus decreasing the sum). This method also ensures no pairs are missed

public class TwoArrSum {
  public static boolean sumExists(int target, int[] arr1, int[] arr2) {
    int pointer1 = 0;
    int pointer2 = arr2.length - 1;
    while (pointer1 <= arr1.length - 1 && pointer2 >= 0) {
      int sum = arr1[pointer1] + arr2[pointer2];
      if (sum < target) {
        pointer1++;
        if (pointer1 == arr1.length) {
          pointer1 = arr1.length - 1;
        }
      } else if (sum > target) {
        pointer2--;
        if (pointer2 == -1) {
          pointer2 = 0;
        }
      } else {
        return true;
      }
    }
    return false;
  }

  public static void main(String[] args) {
    int[] arr1 = {1, 3, 4, 7};
    int[] arr2 = {2, 4, 6, 8};
    int arg = Integer.parseInt(args[0]);
    System.out.println(sumExists(arg, arr1, arr2));
  }
}

package javapgrms;

import java.util.HashMap;

public class targetvaluefrom2list {

public static void main(String[] args) {
int[] list1={2,3,4,5,6,7,8};
int[] list2={3,4,1,2,0,5,7};
int target =7;
HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
int count=0;
for(int i=0;i<list1.length;i++){
for(int j=0;j<list2.length;j++){
int sum = list1[i]+list2[j];
if(sum == target){
hm.put(list1[i], list2[j]);
count++;
}
}
}
System.out.println("no of target sum values are :" +count);
for(int c : hm.keySet()){
System.out.println(c + ":" + hm.get(c));
}
}

}

package javapgrms;

import java.util.HashMap;

public class targetvaluefrom2list {

	public static void main(String[] args) {
		int[] list1={2,3,4,5,6,7,8};
		int[] list2={3,4,1,2,0,5,7};
		int target =7;
		HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
		int count=0;
		for(int i=0;i<list1.length;i++){
			for(int j=0;j<list2.length;j++){
				int sum = list1[i]+list2[j];
				if(sum == target){
				hm.put(list1[i], list2[j]);
					count++;
				}
			}
		}
		System.out.println("no of target sum values are :" +count);
		 for(int c : hm.keySet()){
			 System.out.println(c + ":" + hm.get(c));
		 }
	}

}

public class targetvaluefrom2list {

	public static void main(String[] args) {
		int[] list1={2,3,4,5,6,7,8};
		int[] list2={3,4,1,2,0,5,7};
		int target =7;
		HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
		int count=0;
		for(int i=0;i<list1.length;i++){
			for(int j=0;j<list2.length;j++){
				int sum = list1[i]+list2[j];
				if(sum == target){
				hm.put(list1[i], list2[j]);
					count++;
				}
			}
		}
		System.out.println("no of target sum values are :" +count);
		 for(int c : hm.keySet()){
			 System.out.println(c + ":" + hm.get(c));
		 }
	}

}

Of course there is the obvious n*m solution but we can do a n + m solution if we substract the values out of the total and store the values in a hash set and then look up the value of the other list.

Here is a solution in C#:

public bool IsSumPossibe(int[] nA, int[] mA, int total)
	{
		var substract = new HashSet<int>();
		foreach(var n in nA)
		{
			substract.Add(total - n);
			
		}

		if(divided.Count == 0) return false;

		foreach(var m in mA)
		{
			if(substract.Contains(m))
			{
				return true;
			}
		}

		return false;
	}

import java.util.Scanner;

  class G_Target{
  public static void main(String s[]){

  Scanner sc = new Scanner(System.in);

  System.out.print("enter the size of lists\n");
  int i = sc.nextInt();
  System.out.print("enter the target value: ");
  int h = sc.nextInt();

  int list1[] = new int[i];
  int list2[] = new int[i];
  int list3[] = new int[i];
  int j,k,l=0;
  System.out.print("enter the element of list1 \n");
  for(k=0;k<i;k++){
  list1[k] = sc.nextInt();
  }
  System.out.print("enter the element of list2 \n");
  for(k =0;k<i;k++){
  list2[k] = sc.nextInt();
  }
  for(k=0;k<i;k++){
  list3[k] = list1[k]+list2[k];
  System.out.print(" "+list3[k]+"\n");
  }
  for(k=0;k<i;k++){
  if(list3[k] == h){
  System.out.print(" Target Find");
  break;}
  else{
  System.out.print("Target not there");
  break;}
  }

  System.out.print("\n");
  }
 }

Easy and clean code:

public boolean existsPair(int[] array1, int[] array2){
	Hashset<Integer> set = new Hashset<>();

	for(int num : array1)
		set.add(num);

	for(int num : array2)
		if(set.contains(-num))
			return true;

	return false;

}

def find_sum(l1, l2, val):
    search_dict = set(l2)
    for x in l1:
        if val - x in search_dict:
            return True
    return False
    
a = [1,2,3,4,5,6,7,8,9,10]
b = [11,12,13,14,15,16,17,18,19,20]
print find_sum(a, b, 15)

3 line Python solution

def in_combo(l1, l2, t):
    s1 = set([t-l for l in l1])
    return len(s1.intersection(set(l2))) == 1

A C++ solution

This strategy builds a list of values needed to reach the sum. The second loop searches the sum list for each value. The trick is to take advantage of hash maps (unordered_set), although if space concerns exist, a binary search tree can be used instead (set).

Using std::unordered_set
Time: O(n) to O(n^2)
Space: O(n)

Using std::set
Time: O(nlogn)
Space: O(n)

bool check(int list1[], int list2[], int sum,
           int count1, int count2)
{
  // Corner/Edge cases
  if (sum <= 0 || count1 < 1 || count2 < 0) return false;
  
  // Create a list of sum values needed for the second list
  std::unordered_set<int> sums;
  
  // Add the needed sum values to a hash map
  for (int i = 0; i < count1; ++i)
    if (list1[i] <= sum)
      sums.insert(sum - list1[i]);

  // Check each value in list2 if it exists in the hash map
  for (int i = 0; i < count2; ++i)
    if (sums.find(list2[i]) != sums.end())
      return true;
  
  return false;
}

public boolean isTargetFound(){
List<Integer> list1=Arrays.asList(10,02,73,46,5,16,7,8,29);
List<Integer> list2=Arrays.asList(11,2,31,4,5,56,7,88,29);

Scanner scan=new Scanner(System.in);
int targetValue=scan.nextInt();
System.out.println("targetValue>>>>>>>>>"+targetValue);
for(int i=1;i<list1.size();i++){

if(list2.contains(targetValue-list1.get(i))){
System.out.println("here u go>>targetValue>>"+targetValue);
System.out.println("here u go>>list1.get(i))>>"+list1.get(i));
System.out.println("here u go>>>>"+(targetValue-list1.get(i)));
return true;
}
}

return false;
}
public static void main(String args[]){

WAPSumbetweentwoLists w=new WAPSumbetweentwoLists();
boolean isfound=w.isTargetFound();
//sysout();
System.out.println("isfound>>>>>>"+isfound);
}

import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class WAPSumbetweentwoLists {

public boolean isTargetFound(){
List<Integer> list1=Arrays.asList(10,02,73,46,5,16,7,8,29);
List<Integer> list2=Arrays.asList(11,2,31,4,5,56,7,88,29);

Scanner scan=new Scanner(System.in);
int targetValue=scan.nextInt();
System.out.println("targetValue>>>>>>>>>"+targetValue);
for(int i=1;i<list1.size();i++){

if(list2.contains(targetValue-list1.get(i))){
System.out.println("here u go>>targetValue>>"+targetValue);
System.out.println("here u go>>list1.get(i))>>"+list1.get(i));
System.out.println("here u go>>>>"+(targetValue-list1.get(i)));
return true;
}
}

return false;
}
public static void main(String args[]){

WAPSumbetweentwoLists w=new WAPSumbetweentwoLists();
boolean isfound=w.isTargetFound();
//sysout();
System.out.println("isfound>>>>>>"+isfound);
}

}

Here is the most simple solution....but it takes you to o(n) worst case and best case o(1)

trial

int x = 8;

In your code, you don't have to sort both the arrays, sorting one array is sufficient, like the code I have written.

#include "stdafx.h"
#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;
class Solution {
public:
	int target=35;
	int search(int num,vector<int> v2) {
		int low = 0;
		int high = v2.size()-1;
		int mid;
		while (low <= high) {
			mid = (low + high) / 2;
			if (v2[mid] == num)
				return 1;
			if (num > v2[mid])
				low = mid + 1;
			else
				high = mid - 1;
		}
		return 0;
	}
	bool exists(vector<int> v1, vector<int> v2) {
		std::sort(v2.begin(), v2.end());
		for (int i = 0; i < v2.size(); i++) {
			if (search(target - i,v2))
				return 1;
		}
		return 0;
	}
};
int main()
{
	Solution s;
	cout<<s.exists({ 10,20,2,1,3,4,42,23,24 }, { 4,5,2,0,22,32,-1 });
    return 0;
}

#include "stdafx.h"
     #include "iostream"
#include "vector"
#include "algorithm"
using namespace std;
class Solution {
public:
	int target=35;
	int search(int num,vector<int> v2) {
		int low = 0;
		int high = v2.size()-1;
		int mid;
		while (low <= high) {
			mid = (low + high) / 2;
			if (v2[mid] == num)
				return 1;
			if (num > v2[mid])
				low = mid + 1;
			else
				high = mid - 1;
		}
		return 0;
	}
	bool exists(vector<int> v1, vector<int> v2) {
		std::sort(v2.begin(), v2.end());
		for (int i = 0; i < v2.size(); i++) {
			if (search(target - i,v2))
				return 1;
		}
		return 0;
	}
};
int main()
{
	Solution s;
	cout<<s.exists({ 10,20,2,1,3,4,42,23,24 }, { 4,5,2,0,22,32,-1 });
    return 0;
}

private static boolean isTargetsumExists(int[] list1, int[] list2, int target) {
		Map<Integer,Integer> map = new HashMap<Integer,Integer>();	
		 
		for (int i : list1) {
			map.put(Math.abs(i), i);
		}
		 
		for (int j : list2) {
			if(map.get(Math.abs(target-j)) != null ) {
				return true;
			}
		}
		return false;
	}

Here is the most simple solution....but it takes you to o(n) worst case and best case o(1)...

import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class WAPSumbetweentwoLists {

public boolean isTargetFound(){
List<Integer> list1=Arrays.asList(10,02,73,46,5,16,7,8,29);
List<Integer> list2=Arrays.asList(11,2,31,4,5,56,7,88,29);

Scanner scan=new Scanner(System.in);
int targetValue=scan.nextInt();
System.out.println("targetValue>>>>>>>>>"+targetValue);
for(int i=1;i<list1.size();i++){

if(list2.contains(targetValue-list1.get(i))){
System.out.println("here u go>>targetValue>>"+targetValue);
System.out.println("here u go>>list1.get(i))>>"+list1.get(i));
System.out.println("here u go>>>>"+(targetValue-list1.get(i)));
return true;
}
}

return false;
}
public static void main(String args[]){

WAPSumbetweentwoLists w=new WAPSumbetweentwoLists();
boolean isfound=w.isTargetFound();
//sysout();
System.out.println("isfound>>>>>>"+isfound);
}

}