Arrays Target Sum pairs

#1

Can you please tell me why my code is failing at 2 Cases ,can’t figure it out
import java.util.*;

public class Main {

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int numCases = sc.nextInt();
	int arr[] = new int[numCases];
	for (int i = 1; i <= numCases; i++) {
		arr[i-1]=sc.nextInt();
	}
	int target = sc.nextInt();
	printTargetPairsUsingTreeMap(arr,target);
	sc.close();

}
private static void printTargetPairsUsingTreeMap(int[] arr, int target) {
	TreeMap<Integer,Integer> hm = new TreeMap<Integer,Integer>();
	for (int i = 0; i < arr.length; i++) {
		if(!hm.containsKey(arr[i]))
		{
			hm.put(arr[i],1);
		}
		else
		{
			int val = hm.get(arr[i]);
			hm.remove(arr[i]);
			hm.put(arr[i],val+1);
		}
	}
	for (int i = 0; i < arr.length; i++) {
		if(hm.containsKey(arr[i]))
		{
		int num1= arr[i];
		int num2 = target-num1;
		int t1 = hm.get(arr[i]);
		if(hm.get(num2) != null)
		{
			int t2 = hm.get(num2);
			int max = t2 > t1 ? t2 : t1;
			for(int j=0;j<max;j++)
			{
				System.out.println(num1+" and "+num2);
			}
		}
		hm.remove(num1);
		hm.remove(num2);
		}
	}
	
	
}

}

#2

@shahid.dhariwala,

https://ide.codingblocks.com/s/209281 I have corrected your code.

2 errors:

  1. num1 should not be equal to num2.
    your code was giving wrong answer for this test case:
    5
    5
    2
    3
    4
    1
    6

  2. The first number to be printed should be less than the second number. I have added these 2 conditions in your code.

An alternate approach can be:

1.First sort the given array.
2.Now take two variables one as left and other as right starting from 0th and end index of the sorted array respectively.
3.Now iterate till left<right.

    3.1 Calculate the sum of the elements at left and right position  
    3.1.1 If the sum is equal to the target then print both the elements. //printing target sum pairs  
    3.1.2 If the sum is less than the target then increase the left by 1  
    3.1.3 Else decrease the right by 1
1 Like
#3

Oh my bad, thank you for quick fix. Your alternate approach look less complex than mine :stuck_out_tongue: will go with it :slight_smile:

#4

Yes your approach will give TLE for large test cases.

1 Like