Question

In the java programming language. How would you find if THREE (3) numbers in an array add up to a certain sum so for example if my array element consists of: INPUT: 200, 10, 50, 20 and my output asks if these elements add to: 270? YES (200+50+70) 260? YES (200+10+50) 30? NO What method would you suggest to look through the elements in an array (which im going to add through a text file) and determine if these sums exist in O(n^2)?

Answer 1

This is a Hashing based solution.

• CODE:

(you can edit the code and take input from the file as required)

// Java program to find a triplet using Hashing 
import java.util.*; 

class tripletsum { 

        // returns true if there is triplet 
        // with sum equal to 'sum' present 
        // in A[]. Also, prints the triplet 
        static boolean find3Numbers(int A[],int arr_size, int sum) 
        { 
                // Fix the first element as A[i] 
                for (int i = 0; i < arr_size - 2; i++) { 

                        // Find pair in subarray A[i+1..n-1] 
                        // with sum equal to sum - A[i] 
                        HashSet<Integer> s = new HashSet<Integer>(); 
                        int curr_sum = sum - A[i]; 
                        for (int j = i + 1; j < arr_size; j++) { 
                                if (s.contains(curr_sum - A[j])) { 
                                        System.out.printf("Triplet is %d, %d, %d", A[i],A[j], curr_sum - A[j]); 
                                        return true; 
                                } 
                                s.add(A[j]); 
                        } 
                } 

                // If we reach here, then no triplet was found 
                return false; 
        } 

        /* Driver code */
        public static void main(String[] args) 
        { 
                int A[] = { 1, 4, 45, 6, 10, 8 }; 
                int sum = 22; 
                int arr_size = A.length; 

                find3Numbers(A, arr_size, sum); 
        } 
} 
 

• Approach: This approach uses extra space but is simpler. Run two loops outer loop from start to end and the inner loop from i+1 to end. Create a hashmap or set to store the elements in between i+1 to j-1. So if the given sum is x, check if there is a number in the set which is equal to x – arr[i] – arr[j]. If yes print the triplet.
• Algorithm:
  1. Traverse the array from start to end. (loop counter i)
  2. Create a HashMap or set to store unique pairs.
  3. Run another loop from i+1 to end of the array. (loop counter j)
  4. If there is an element in the set which is equal to x- arr[i] – arr[j], then print the triplet (arr[i], arr[j], x-arr[i]-arr[j]) and break
  5. Insert the jth element in the set.
• Complexity Analysis:
  1. Time complexity: O(N^2).
     There are only two nested loops traversing the array, so time complexity is O(n^2).
  2. Space Complexity: O(1).
     As no extra space is required.