Triplet that sum to a given value in Java

May 2, 2023

Triplet that sum to a Given Value

On this page we will discuss about triplet that sum to a given value in Java. A triplet that sums to a given value C is a set of three elements in an array whose sum is equal to C. We will this in detail we different methods along with algorithm and code in Java.

Triplet that Sum to Given Value in Java

A triplet that sums to a given value is a set of three elements in an array whose sum is equal to the given value. For example, if we have an array [1, 2, 3, 4, 5] and the target sum is 9, then a triplet that sums to 9 could be (2, 3, 4) or (1, 2, 6), as both sets of elements add up to 9. The key requirement is that the sum of the three elements in the triplet is equal to the given value.

On this page we will discuss two different methods for this-

Naive Approach
Sorting Approach

Naive approach: The naive approach for finding sub-arrays with a given sum involves using a nested loop to iterate through all possible sub-arrays of the given array. For each starting index i, it checks all sub-arrays starting from i and ending at different indices j, and calculates the sum of each sub-array. If the sum of a sub-array is equal to the given sum, it prints the indices of the sub-array and returns. If no sub-array is found with the given sum, it prints a message indicating that no sub-array was found.

Algorithm:

Prompt the user to enter the size of the array and store it in a variable, let’s call it ‘n’.
Take ‘n’ integer inputs from the user to populate the array.
Prompt the user to enter an integer value, let’s call it ‘o’.
Use three nested loops, where the first loop iterates from the start to the end of the array (loop counter ‘i’), the second loop iterates from ‘i+1’ to the end of the array (loop counter ‘j’), and the third loop iterates from ‘j+1’ to the end of the array (loop counter ‘k’).
The loop counters ‘i’, ‘j’, and ‘k’ represent the indices of the three elements in the triplet.
Calculate the sum of the ‘i’th, ‘j’th, and ‘k’th elements of the array. If the sum is equal to the given sum, print the triplet and break out of the loops.
If no triplet is found with the given sum, print “No triplet exists”.

Given an array which consists of only 0, 1 and 2

Move all the negative elements to one side of the array

Find the Union and Intersection of the two sorted arrays

Find Largest sum contiguous Subarray

Minimize the maximum difference between heights

Java Code for naive approach

Run

import java.util.*;

public class Main {
    public static void findTriplets(int[] arr, int n, int sum) {
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (arr[i] + arr[j] + arr[k] == sum) {
                        System.out.println("(" + arr[i] + ", " + arr[j] + ", " + arr[k] + ")");
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.print("Array: ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        int sum = 9;
        System.out.println("\nSum: " + sum);
        System.out.println("Triplets:");
        findTriplets(arr, arr.length, sum);
    }
}

Output

Array: 1 2 3 4 5 
sum: 9
Triplets:
(1, 3, 5)
(2, 3, 4)

sorting approach: The sorting approach involves sorting the given array and then using two pointers to find triplets that sum to the given value Java. This approach has a time complexity of O(n^2), where n is the size of the array.

Algorithm:

Sort the given array in ascending order using insertion sort.
Iterate through the array from the beginning till the third-to-last element.
For each element, use two pointers to find pairs that sum up to the given value.
Print the triplet if found.
If the sum is less, increment the first pointer; if the sum is greater, decrement the second pointer.
Repeat steps 3-5 until the two pointers cross each other.
Continue the iteration until all possible triplets are checked.
Print the array elements and the given sum.
Call the function to find and print the triplets.
Return 0 to indicate successful execution of the program.

Java Code for sorting approach

Run

import java.util.Arrays;

public class Main {
    
    public static void sort(int arr[], int n) {
        int i, element, j;
        for (i = 1; i < n; i++) {
            element = arr[i];
            j = i - 1;
            while (j >= 0 && arr[j] > element) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = element;
        }
    }
    
    public static void findTriplets(int arr[], int n, int sum) {
        sort(arr, n);
        for (int i = 0; i < n - 2; i++) {
            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                if (arr[i] + arr[j] + arr[k] == sum) {
                    System.out.println("(" + arr[i] + ", " + arr[j] + ", " + arr[k] + ")");
                    j++;
                    k--;
                } else if (arr[i] + arr[j] + arr[k] < sum) {
                    j++;
                } else {
                    k--;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int arr[] = {1, 2, 3, 4, 5};
        int n = arr.length;
        int sum = 9;
        
        System.out.print("Array: ");
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        
        System.out.println("\nSum: " + sum);
        System.out.println("Triplets:");
        findTriplets(arr, n, sum);
    }
}

Output

Array: 1 2 3 4 5 
sum: 9
Triplets:
(1, 3, 5)
(2, 3, 4)

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Introduction to Trees

Binary Trees

Binary Tree in Data Structures (Introduction)
Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
Inorder Postorder PreOrder Traversals Examples
- Inorder Tree Traversal in Binary Tree: C | C++ | Java
- Preorder Tree Traversal in Binary Tree : C | C++ | Java
- Postorder Tree Traversal in Binary Tree : C | C++ | Java
Tree Traversal without Recursion
- Postorder Preorder Inorder Traversal without recursion
- Inorder Tree Traversal without Recursion – C | C++ | Java
- Preorder Tree Traversal without Recursion – C | C++ | Java
- Postorder Tree Traversal without Recursion – C | C++ | Java

Binary Search Trees

Binary search tree in Data Structures (Introduction)
- BST: Introduction to Binary Search Tree
- BST: Binary Search Tree Program : C | C++ | Java
- BST: Search a node in Binary Search Tree : C | C++ | Java
- BST: Insertion in a Binary Search Tree : C | C++ | Java
- BST: Deletion in a Binary Search Tree : C | C++ | Java

Traversals

Traversal in Trees
Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
Tree Traversals: Depth First Search (DFS) : C | C++ | Java
Construct a Binary Tree from Postorder and Inorder

B – Trees

B-Tree
- B-Tree: Introduction
- B-Tree: Insertion : C | C++ | Java
- B-Tree: Deletion : C | C++ | Java

AVL Trees

AVL Trees
- AVL Trees: Introduction
- AVL Tree Insertion : C | C++ | Java
- AVL Tree Deletion : C | C++ | Java
- Insertion in a Binary Tree (Level Order) – C | C++ | Java
- Searching in Binary Tree – C | C++ | Java
- Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

Depth First Traversals – C | C++ | Java
Level Order Traversal – C | C++ | Java
Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
Find size of the Binary tree – C | C++ | Java
Find the height of binary tree – C | C++ | Java
Find maximum in binary tree – C | C++ | Java
Check whether two tree are identical- C| C++| Java
Spiral Order traversal of Tree- C | C++| Java
Level Order Traversal Line by Line – C | C++| Java
Hand shaking lemma and some Impotant Tree Properties.
Check If binary tree if Foldable or not.- C| C++| Java
check whether tree is Symmetric – C| C++| Java.
Check for Children-Sum in Binary Tree- C|C++| Java
Sum of all nodes in Binary Tree- C | C++ | Java
Lowest Common Ancestor in Binary Tree- C | C++ | Java