Assignment 4 Solution

Question 1 Given an unsorted list of n elements, find the first element, which is repeated

Without Comments

public class Q1 {
    public static void main(String[] args) {
        int[] arr = { 34, 56, 77, 1, 5, 6, 6, 6, 7, 8, 10, 34, 20, 30 };
        System.out.print("First element which is repeated is : "+FirstRepeated(arr));
    }

    static int FirstRepeated(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] == arr[j]) {
                    return arr[i];
                }
            }
        }
        return 0;
    }
}

With comments

public class Q1 {
    public static void main(String[] args) {
        // create an array of integers
        int[] arr = { 34, 56, 77, 1, 5, 6, 6, 6, 7, 8, 10, 34, 20, 30 };
        
        // call the `FirstRepeated` function and print its return value
        System.out.print("First element which is repeated is : "+FirstRepeated(arr));
    }

    // function to find the first repeated element in an array
    static int FirstRepeated(int[] arr) {
        // iterate through the array to compare each element with the rest of the elements
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                // if two elements are equal, then return that element as it is the first repeated element
                if (arr[i] == arr[j]) {
                    return arr[i];
                }
            }
        }
        // if there is no repeated element in the array, return 0
        return 0;
    }
}

Credit:

Question 2 Given an array of n numbers, print the duplicate elements in the array

Without Comments

import java.util.Arrays;

public class FindRepeatingNumbers {
    public static void main(String[] args) {
        int[] numbers = { 34, 56, 77, 1, 5, 6, 6, 6, 7, 8, 10, 34, 20, 30 };
        printRepeatingNumbers(numbers);
    }

    public static void printRepeatingNumbers(int[] numbers) {
        Arrays.sort(numbers);
        
        System.out.print("Repeating elements are : ");
        
        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] == numbers[i - 1]) {
                System.out.print(numbers[i] + " ");
            }
        }
    }
}

With comments

import java.util.Arrays;

public class FindRepeatingNumbers {
    public static void main(String[] args) {
        int[] numbers = { 34, 56, 77, 1, 5, 6, 6, 6, 7, 8, 10, 34, 20, 30 };
        printRepeatingNumbers(numbers);
    }

    public static void printRepeatingNumbers(int[] numbers) {
        // Sort the array in ascending order to make it easier to find repeating numbers
        Arrays.sort(numbers);
        
        System.out.print("Repeating elements are : ");
        
        // Iterate through the sorted array, checking if the current element is the same as the previous element
        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] == numbers[i - 1]) {
                System.out.print(numbers[i] + " ");
            }
        }
    }
}

Credit:

Question 4 Write a program to remove duplicate from an integer list

Without Comments

import java.util.Arrays;

public class RemoveDuplicateElements {

    public static void main(String[] args) {
        int[] originalArray = { 34, 56, 77, 1, 5, 6, 6, 6, 7, 8, 10, 34, 20, 30 };
        
        System.out.print("The array is: ");
        print(originalArray);
        
        System.out.print("After removal of duplicates: ");
        int[] withoutDuplicates = removeDuplicates(originalArray);
        print(withoutDuplicates);
    }

    public static int[] removeDuplicates(int[] arr) {
        int j = 0;
        Arrays.sort(arr);
        
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != arr[j]) {
                j++;
                arr[j] = arr[i];
            }
        }
        
        int[] resultArray = Arrays.copyOf(arr, j + 1);
        return resultArray;
    }

    static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

With comments

import java.util.Arrays;

public class RemoveDuplicateElements {

    public static void main(String[] args) {
        int[] originalArray = { 34, 56, 77, 1, 5, 6, 6, 6, 7, 8, 10, 34, 20, 30 };
        
        // Print the original array
        System.out.print("The array is: ");
        print(originalArray);
        
        // Print the array after removal of duplicates
        System.out.print("After removal of duplicates: ");
        int[] withoutDuplicates = removeDuplicates(originalArray);
        print(withoutDuplicates);
    }

    public static int[] removeDuplicates(int[] arr) {
        int j = 0; // Index of last non-duplicate element found so far in the array
        Arrays.sort(arr); // Sort the array in ascending order to make duplicate elements adjacent
        
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != arr[j]) { // Check if the current element is a duplicate or not
                j++;
                arr[j] = arr[i]; // If it's not a duplicate, copy it to the next available index in the result array
            }
        }
        
        // Create and return a new array containing only the non-duplicate elements
        int[] resultArray = Arrays.copyOf(arr, j + 1);
        return resultArray;
    }

    // Helper method to print an int array
    static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Credit:

Question 5 In given list of n - 1 elements, which are in the range of 1 to n. There are no duplicates in the array. One of the integer is missing. Find the missing element

Without Comments

public class Q5 {
    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 6, 7, 8, 9, 10 };
        System.out.print("The missing number in the array is : "+findMiss(arr));
    }

    static int findMiss(int[] arr) {
        for (int i = arr[0] - 1; i < arr.length; i++) {
            if (arr[i] != i + 1) {
                return i + 1;
            }
        }
        return Integer.MIN_VALUE;
    }
}

With comments

public class Q5 {
    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 6, 7, 8, 9, 10 };
        // Print the missing number in the array.
        System.out.print("The missing number in the array is : "+findMiss(arr));
    }

    static int findMiss(int[] arr) {
        // Initialize the loop counter to the first element of the array minus 1.
        for (int i = arr[0] - 1; i < arr.length; i++) {
            // If the current element is not equal to the expected value, return the expected value.
            if (arr[i] != i + 1) {
                return i + 1;
            }
        }
        // If no missing number is found, return the minimum value of the integer data type.
        return Integer.MIN_VALUE;
    }
}

Credit:

Question 6 Given an array, find the maximum and minimum value in the array and also find the values in range minimum and maximum that are absent in the array

Without Comments

import java.util.Arrays;

public class FindMinMaxMissing {
    
    public static void main(String[] args) {
        int[] arr = { 10, 7, 5, 9, 4, 20, 15, 13 };
        
        System.out.println("The maximum and minimum element in the array is...");
        findMinMax(arr);
    }

    static void findMinMax(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        
        System.out.println("Maximum value : " + max);
        System.out.println("Minimum value : " + min);
        
        System.out.println("The missing elements between min and max : ");
        findMissingElements(arr);
    }

    static void findMissingElements(int[] arr) {
        Arrays.sort(arr);
        int current = arr[0];
        int i = 0;
        
        while (i < arr.length) {
            if (current == arr[i]) {
                current++;
                i++;
            } else {
                System.out.print(current + " ");
                current++;
            }
        }
    }
}

With comments

import java.util.Arrays;

public class FindMinMaxMissing {
    
    public static void main(String[] args) {
        int[] arr = { 10, 7, 5, 9, 4, 20, 15, 13 };
        
        // Output the maximum and minimum elements in the array
        System.out.println("The maximum and minimum element in the array is...");
        findMinMax(arr);
    }

    static void findMinMax(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        
        // Loop through the array to find the minimum and maximum elements
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        
        // Output the minimum and maximum elements
        System.out.println("Maximum value : " + max);
        System.out.println("Minimum value : " + min);
        
        // Output the missing elements between the minimum and maximum elements
        System.out.println("The missing elements between min and max : ");
        findMissingElements(arr);
    }

    static void findMissingElements(int[] arr) {
        Arrays.sort(arr);
        int current = arr[0];
        int i = 0;
        
        // Loop through the array to find the missing elements between the minimum and maximum elements
        while (i < arr.length) {
            if (current == arr[i]) {
                current++;
                i++;
            } else {
                System.out.print(current + " ");
                current++;
            }
        }
    }
}

Credit:

Question 7 Given an array in which all the elements appear even number of times except one, which appear odd number of times. Find the element which appear odd number of times

Without Comments

import java.util.HashMap;

public class FindOddCount {
    
    public static void main(String[] args) {
        int[] arr = { 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 };
        findOddCount(arr);
    }

    static void findOddCount(int[] arr) {
        HashMap<Integer, Integer> countMap = new HashMap<>();
        
        for (int i = 0; i < arr.length; i++) {
            if (countMap.containsKey(arr[i]))
                countMap.put(arr[i], countMap.get(arr[i]) + 1);
            else
                countMap.put(arr[i], 1);
        }
        
        System.out.print("The number appearing odd number of times is : ");
        for (int i = 0; i < arr.length; i++) {
            if (countMap.containsKey(arr[i]) && (countMap.get(arr[i]) % 2 == 1)) {
                System.out.println(arr[i]);
                break;
            }
        }
    }
}

With comments

import java.util.HashMap;

public class FindOddCount {
    
    public static void main(String[] args) {
        int[] arr = { 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 };
        findOddCount(arr);
    }

    static void findOddCount(int[] arr) {
        HashMap<Integer, Integer> countMap = new HashMap<>();
        
        // Loop through the array and count the occurrence of each element
        for (int i = 0; i < arr.length; i++) {
            if (countMap.containsKey(arr[i]))
                countMap.put(arr[i], countMap.get(arr[i]) + 1);
            else
                countMap.put(arr[i], 1);
        }
        
        // Loop through the array to find the element appearing odd number of times
        System.out.print("The number appearing odd number of times is : ");
        for (int i = 0; i < arr.length; i++) {
            if (countMap.containsKey(arr[i]) && (countMap.get(arr[i]) % 2 == 1)) {
                System.out.println(arr[i]);
                break;
            }
        }
    }
}

Credit:

Question 8 Given an array in which all the elements appear even number of times except two, which appear odd number of times. Find the elements which appear odd number of times in O(n) time complexity and O(1) space complexity

Without Comments

public class FindOddOccurrence {

    public static void main(String[] args) {

        int[] numbers = {2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2};
        int arrayLength = numbers.length;

        System.out.println("The number appearing an odd number of times is: " + findOddOccurrence(numbers, arrayLength));
    }

    static int findOddOccurrence(int[] numbers, int arrayLength) {

        int result = 0;

        for (int i = 0; i < arrayLength; i++) {
            result ^= numbers[i];
        }

        return result;
    }
}

With comments

public class FindOddOccurrence {

    public static void main(String[] args) {

        // Initialize the array
        int[] numbers = {2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2};
        int arrayLength = numbers.length;

        // Call the method to find the odd occurrence and print the result
        System.out.println("The number appearing an odd number of times is: " + findOddOccurrence(numbers, arrayLength));
    }

    static int findOddOccurrence(int[] numbers, int arrayLength) {

        int result = 0;

        // Iterate through the array
        for (int i = 0; i < arrayLength; i++) {

            // XOR operation on all the numbers in the array
            result ^= numbers[i];
        }

        // Return the result
        return result;
    }
}

Credit:

Question 9 Given an array of size N, the elements in the array may be repeated. You need to find sum of distinct elements of the array. If there is some value repeated continuously then they should be added once

Without Comments

import java.util.Arrays;

public class SumOfDistinctElements {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 2, 3, 3, 3, 4, 4, 5};
        int sum = 0;
        boolean isContinuous = false;

        Arrays.sort(numbers);

        for (int i = 0; i < numbers.length; i++) {
            if (i < numbers.length - 1 && numbers[i] == numbers[i + 1]) {
                isContinuous = true;
            } else {
                if (!isContinuous) {
                    sum += numbers[i];
                }
                isContinuous = false;
            }
        }

        System.out.println("Sum of distinct elements: " + sum);
    }
}

With comments

import java.util.Arrays;

public class SumOfDistinctElements {

    public static void main(String[] args) {

        // Initialize the array
        int[] numbers = {1, 2, 2, 3, 3, 3, 4, 4, 5};
        int sum = 0;
        boolean isContinuous = false;

        // Sort the array
        Arrays.sort(numbers);

        // Iterate through the array
        for (int i = 0; i < numbers.length; i++) {

            // Check if the current element is the same as the next element
            if (i < numbers.length - 1 && numbers[i] == numbers[i + 1]) {
                isContinuous = true;
            } else {
                // If the current element is not the same as the next element, and the current element is not continuous,
                // add the current element to the sum
                if (!isContinuous) {
                    sum += numbers[i];
                }
                // Set isContinuous back to false
                isContinuous = false;
            }
        }

        // Print the sum of distinct elements
        System.out.println("Sum of distinct elements: " + sum);
    }
}

Credit:

Question 10 In given List of integers, both +ve and -ve. You need to find the two elements such that their sum is closest to zero

Without Comments

import java.util.*;

public class ClosestToZeroSum {

    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(-10, -5, 2, 4, 7, 8);
        int minSum = Integer.MAX_VALUE;
        int num1 = 0;
        int num2 = 0;

        Collections.sort(numbers);

        int left = 0;
        int right = numbers.size() - 1;

        while (left < right) {
            int sum = numbers.get(left) + numbers.get(right);

            if (Math.abs(sum) < Math.abs(minSum)) {
                minSum = sum;
                num1 = numbers.get(left);
                num2 = numbers.get(right);
            }

            if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }

        System.out.println("Two elements with sum closest to zero: " + num1 + " and " + num2);
    }
}

With comments

import java.util.*;

public class ClosestToZeroSum {

    public static void main(String[] args) {

        // Initialize the list of numbers
        List<Integer> numbers = Arrays.asList(-10, -5, 2, 4, 7, 8);
        int minSum = Integer.MAX_VALUE;
        int num1 = 0;
        int num2 = 0;

        // Sort the list in ascending order
        Collections.sort(numbers);

        // Set the left pointer to the beginning of the list, and the right pointer to the end of the list
        int left = 0;
        int right = numbers.size() - 1;

        // Loop through the list with two pointers
        while (left < right) {

            // Calculate the sum of the two current elements
            int sum = numbers.get(left) + numbers.get(right);

            // If the absolute value of the sum is smaller than the minimum sum seen so far, update the minimum sum and the two numbers
            if (Math.abs(sum) < Math.abs(minSum)) {
                minSum = sum;
                num1 = numbers.get(left);
                num2 = numbers.get(right);
            }

            // If the sum is negative, increment the left pointer
            if (sum < 0) {
                left++;
            } else { // Otherwise, decrement the right pointer
                right--;
            }
        }

        // Print the two elements with sum closest to zero
        System.out.println("Two elements with sum closest to zero: " + num1 + " and " + num2);
    }
}

Credit:

Question 11 Given an array of n numbers, find two elements such that their sum is equal to “value”

Without Comments

import java.util.*;

public class TwoSum {

    public static void main(String[] args) {
        int[] arr = { 2, 7, 11, 15, 8, 3 };
        int target = 10;

        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < arr.length; i++) {
            int complement = target - arr[i];

            if (map.containsKey(complement)) {
                int complementIndex = map.get(complement);
                System.out.println("Two elements with sum " + target + " are " + arr[complementIndex] + " and " + arr[i]);
                return;
            }

            map.put(arr[i], i);
        }

        System.out.println("No two elements found with sum " + target);
    }
}

With comments

import java.util.*;

public class TwoSum {

    public static void main(String[] args) {

        // Initialize the array and target value
        int[] arr = { 2, 7, 11, 15, 8, 3 };
        int target = 10;

        // Create a HashMap to store the complement and its index
        HashMap<Integer, Integer> map = new HashMap<>();

        // Loop through the array
        for (int i = 0; i < arr.length; i++) {

            // Calculate the complement of the current element
            int complement = target - arr[i];

            // If the complement is already in the HashMap, print the two elements and return
            if (map.containsKey(complement)) {
                int complementIndex = map.get(complement);
                System.out.println("Two elements with sum " + target + " are " + arr[complementIndex] + " and " + arr[i]);
                return;
            }

            // Add the current element and its index to the HashMap
            map.put(arr[i], i);
        }

        // If no two elements are found with the given sum, print a message indicating so
        System.out.println("No two elements found with sum " + target);
    }
}

Credit:

Question 12 Given two lists X and Y, find a pair of elements (xi, yi) such that xi ∈ X and yi ∈ Y, where xi + yi = value

Without Comments

import java.util.*;

public class Q12 {
    public static void main(String[] args) {
        List<Integer> list1 = Arrays.asList(1, 2, 3, 4, 5);
        List<Integer> list2 = Arrays.asList(6, 7, 8, 9, 10);
        int targetSum = 11;
        Set<Integer> set2 = new HashSet<>();
        
        for (int num : list2) {
            set2.add(num);
        }
        
        for (int num : list1) {
            int complement = targetSum - num;
            if (set2.contains(complement)) {
                System.out.println("Pair with sum " + targetSum + ": (" + num + ", " + complement + ")");
                break;
            }
        }
    }
}

With comments

import java.util.*;

public class Q12 {
    public static void main(String[] args) {
        List<Integer> list1 = Arrays.asList(1, 2, 3, 4, 5);
        List<Integer> list2 = Arrays.asList(6, 7, 8, 9, 10);
        int targetSum = 11;
        Set<Integer> set2 = new HashSet<>();
        
        // add all elements of list2 to a set
        for (int num : list2) {
            set2.add(num);
        }
        
        // iterate over elements of list1 and check if their complement exists in set2
        for (int num : list1) {
            int complement = targetSum - num;
            if (set2.contains(complement)) {
                System.out.println("Pair with sum " + targetSum + ": (" + num + ", " + complement + ")");
                break;
            }
        }
    }
}

Credit:

Question 13 Given an array of integers, find the element pair with minimum difference

Without Comments

import java.util.*;

public class Q13 {
    public static void main(String[] args) {
        int[] arr = { 5, 1, 3, 9, 7 };
        Arrays.sort(arr);
        int minDiff = Integer.MAX_VALUE;
        int elem1 = 0;
        int elem2 = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            int diff = arr[i + 1] - arr[i];
            if (diff < minDiff) {
                minDiff = diff;
                elem1 = arr[i];
                elem2 = arr[i + 1];
            }
        }
        System.out.println("Pair with minimum difference: (" + elem1 + ", " + elem2 + ")");
    }
}

With comments

import java.util.*;

public class Q13 {
    public static void main(String[] args) {
        // Array of integers
        int[] arr = { 5, 1, 3, 9, 7 };
        
        // Sort the array in ascending order
        Arrays.sort(arr);
        
        // Initialize minimum difference, and elements to hold pair with min difference
        int minDiff = Integer.MAX_VALUE;
        int elem1 = 0;
        int elem2 = 0;

        // Find the minimum difference between adjacent elements in the sorted array
        for (int i = 0; i < arr.length - 1; i++) {
            int diff = arr[i + 1] - arr[i];
            if (diff < minDiff) {
                minDiff = diff;
                elem1 = arr[i];
                elem2 = arr[i + 1];
            }
        }

        // Output the pair with the minimum difference
        System.out.println("Pair with minimum difference: (" + elem1 + ", " + elem2 + ")");
    }
}

Credit:

Question 14 Given two array, find minimum difference pair such that it should take one element from each array

Without Comments

import java.util.*;

public class FindMinimumDifferencePair {
    
    public static void main(String[] args) {
        int[] arr1 = { 5, 1, 3, 9, 7 };
        int[] arr2 = { 8, 2, 6, 10, 4 };
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        int minDiff = Integer.MAX_VALUE;
        int elem1 = 0;
        int elem2 = 0;
        int i = 0;
        int j = 0;
        while (i < arr1.length && j < arr2.length) {
            int diff = Math.abs(arr1[i] - arr2[j]);
            if (diff < minDiff) {
                minDiff = diff;
                elem1 = arr1[i];
                elem2 = arr2[j];
            }
            if (arr1[i] < arr2[j]) {
                i++;
            } else {
                j++;
            }
        }
        System.out.println("Pair with minimum difference: " + elem1 + ", " + elem2);
    }
}

With comments

import java.util.*;

public class FindMinimumDifferencePair {
    
    public static void main(String[] args) {
        int[] arr1 = { 5, 1, 3, 9, 7 };
        int[] arr2 = { 8, 2, 6, 10, 4 };
        
        // Sort the arrays in ascending order
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        
        // Initialize variables to track the minimum difference and corresponding elements
        int minDiff = Integer.MAX_VALUE;
        int elem1 = 0;
        int elem2 = 0;
        int i = 0;
        int j = 0;
        
        // Traverse both arrays and find the pair with the minimum difference
        while (i < arr1.length && j < arr2.length) {
            int diff = Math.abs(arr1[i] - arr2[j]);
            if (diff < minDiff) {
                minDiff = diff;
                elem1 = arr1[i];
                elem2 = arr2[j];
            }
            if (arr1[i] < arr2[j]) {
                i++;
            } else {
                j++;
            }
        }

        // Print the pair with the minimum difference
        System.out.println("Pair with minimum difference: " + elem1 + ", " + elem2);
    }
}

Credit:

Question 15 Given an array of integers, you need to find a triplet whose sum 0

Without Comments

import java.util.*;

public class Q15 {
    public static void main(String[] args) {
        int[] arr = { 5, -3, 2, -8, 1, 6, -1, 3 };
        
        Arrays.sort(arr);
        
        List<List<Integer>> triplets = new ArrayList<>();
        
        for (int i = 0; i < arr.length - 2; i++) {
            if (i == 0 || (i > 0 && arr[i] != arr[i - 1])) {
                int l = i + 1;
                int h = arr.length - 1;
                int sum = 0 - arr[i];
                
                while (l < h) {
                    if (arr[l] + arr[h] == sum) {
                        triplets.add(Arrays.asList(arr[i], arr[l], arr[h]));
                        
                        while (l < h && arr[l] == arr[l + 1]) {
                            l++;
                        }
                        while (l < h && arr[h] == arr[h - 1]) {
                            h--;
                        }
                        
                        l++;
                        h--;
                    } else if (arr[l] + arr[h] < sum) {
                        l++;
                    } else {
                        h--;
                    }
                }
            }
        }

        System.out.println("Triplets whose sum is 0:");
        for (List<Integer> triplet : triplets) {
            System.out.println(triplet);
        }
    }
}

With comments

import java.util.*;

public class Q15 {
    public static void main(String[] args) {
        int[] arr = { 5, -3, 2, -8, 1, 6, -1, 3 };
        
        // Sort the array in ascending order
        Arrays.sort(arr);
        
        // Create a list to store the unique triplets whose sum is 0
        List<List<Integer>> triplets = new ArrayList<>();
        
        // Loop through the array up to the third last element
        for (int i = 0; i < arr.length - 2; i++) {
            // Skip over duplicates of the same number
            if (i == 0 || (i > 0 && arr[i] != arr[i - 1])) {
                int l = i + 1; // Set the left pointer to the next element after the current element
                int h = arr.length - 1; // Set the right pointer to the last element in the array
                int sum = 0 - arr[i]; // Calculate the sum needed to make the triplet equal 0
                
                // Loop through the remaining elements with two pointers
                while (l < h) {
                    if (arr[l] + arr[h] == sum) { // If the sum of the two pointers plus the current element equals 0
                        triplets.add(Arrays.asList(arr[i], arr[l], arr[h])); // Add the triplet to the list
                        
                        // Skip over duplicates of the left and right pointers
                        while (l < h && arr[l] == arr[l + 1]) {
                            l++;
                        }
                        while (l < h && arr[h] == arr[h - 1]) {
                            h--;
                        }
                        
                        l++; // Move the left pointer to the next element
                        h--; // Move the right pointer to the previous element
                    } else if (arr[l] + arr[h] < sum) { // If the sum is less than the target sum, move the left pointer to the next element
                        l++;
                    } else { // If the sum is greater than the target sum, move the right pointer to the previous element
                        h--;
                    }
                }
            }
        }

        // Print out the triplets whose sum is 0
        System.out.println("Triplets whose sum is 0:");
        for (List<Integer> triplet : triplets) {
            System.out.println(triplet);
        }
    }
}

Credit:

Question 16 Given an array of integers, you need to find a triplet whose sum equal to given value

Without Comments

import java.util.*;

public class Q16 {
    public static void main(String[] args) {
        int[] arr = { 1, 5, 8, 9, 12, 15 };
        int targetSum = 22;
        List<List<Integer>> triplets = new ArrayList<>();

        for (int i = 0; i < arr.length - 2; i++) {
            int left = i + 1;
            int right = arr.length - 1;
            int complement = targetSum - arr[i];

            while (left < right) {
                if (arr[left] + arr[right] == complement) {
                    triplets.add(Arrays.asList(arr[i], arr[left], arr[right]));
                    left++;
                    right--;
                } else if (arr[left] + arr[right] < complement) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        System.out.println("Triplets whose sum is " + targetSum + ":");
        for (List<Integer> triplet : triplets) {
            System.out.println(triplet);
        }
    }
}

With comments

import java.util.*;

public class Q16 {
    public static void main(String[] args) {
        int[] arr = { 1, 5, 8, 9, 12, 15 };
        int targetSum = 22;
        List<List<Integer>> triplets = new ArrayList<>();

        // Iterate over array from first to second-last element
        for (int i = 0; i < arr.length - 2; i++) {
            int left = i + 1;
            int right = arr.length - 1;
            int complement = targetSum - arr[i]; // Calculate the complement to target sum for current element

            // Iterate over the remaining elements
            while (left < right) {
                // If triplet is found, add it to the result list and move pointers to next distinct elements
                if (arr[left] + arr[right] == complement) {
                    triplets.add(Arrays.asList(arr[i], arr[left], arr[right]));
                    left++;
                    right--;
                } 
                // If sum of two elements is less than complement, move left pointer to next distinct element
                else if (arr[left] + arr[right] < complement) {
                    left++;
                } 
                // If sum of two elements is greater than complement, move right pointer to next distinct element
                else {
                    right--;
                }
            }
        }

        // Print the result list
        System.out.println("Triplets whose sum is " + targetSum + ":");
        for (List<Integer> triplet : triplets) {
            System.out.println(triplet);
        }
    }
}

Credit:

Question 17 Given an array of positive integers representing edges of triangles. Find the number of triangles that can be formed from these elements representing sides of triangles. For a triangle sum of two edges is always greater than third edge

Without Comments

import java.util.*;

public class Q17 {

    public static void main(String[] args) {
        int[] arr = { 4, 6, 3, 7, 1, 9, 8, 2, 5 };
        Arrays.sort(arr);
        int triangleCount = 0;
        for (int i = 0; i < arr.length - 2; i++) {
            int k = i + 2;
            for (int j = i + 1; j < arr.length - 1 && arr[i] != 0; j++) {
                while (k < arr.length && arr[i] + arr[j] > arr[k]) {
                    k++;
                }
                triangleCount += k - j - 1;
            }
        }
        System.out.println("Number of triangles that can be formed: " + triangleCount);
    }
}

With comments

import java.util.*;

public class Q17 {
    public static void main(String[] args) {
        int[] arr = { 4, 6, 3, 7, 1, 9, 8, 2, 5 };
        
        // Sort the array in ascending order
        Arrays.sort(arr);
        
        int triangleCount = 0;

        // Iterate through the array using two nested loops
        for (int i = 0; i < arr.length - 2; i++) {
            // Start second loop from i+1
            int k = i + 2;
            for (int j = i + 1; j < arr.length - 1 && arr[i] != 0; j++) {
                // Find the maximum value of k such that the sum of elements at indices i, j, and k is less than or equal to 2 times the value of element at index k.
                while (k < arr.length && arr[i] + arr[j] > arr[k]) {
                    k++;
                }
                
                // Add the count of all valid values of k to the triangle count.
                // Here, we subtract j from k and then subtract 1 to account for the fact that we have already counted the values of k from the previous iterations.
                triangleCount += k - j - 1;
            }
        }

        System.out.println("Number of triangles that can be formed: " + triangleCount);
    }
}

Credit:

Question 18 Suppose you are given an unsorted list of n distinct elements. How will you identify the second largest element with minimum number of comparisons

Without Comments

public class Q18 {
    public static void main(String[] args) {
        int[] arr = { 4, 8, 1, 6, 2, 7, 5, 3 };
        int n = arr.length;
        
        int cmpCount = 0;
        
        int largest = Integer.MIN_VALUE;
        int secondLargest = Integer.MIN_VALUE;
        
        for (int i = 0; i < n; i++) {
            cmpCount++;
            
            if (arr[i] > largest) {
                secondLargest = largest;
                largest = arr[i];
            } else if (arr[i] > secondLargest && arr[i] != largest) {
                secondLargest = arr[i];
            }
        }
        
        System.out.println("Second largest element: " + secondLargest);
        System.out.println("Number of comparisons: " + cmpCount);
    }
}

With comments

public class Q18 {
    public static void main(String[] args) {
        int[] arr = { 4, 8, 1, 6, 2, 7, 5, 3 };
        int n = arr.length;
        
        // variable to count number of comparisons
        int cmpCount = 0;
        
        // initialize largest and secondLargest to minimum value of integer
        int largest = Integer.MIN_VALUE;
        int secondLargest = Integer.MIN_VALUE;
        
        // Iterate through the array
        for (int i = 0; i < n; i++) {
            // increment comparison count for each iteration
            cmpCount++;
            
            // if current element is greater than largest element
            if (arr[i] > largest) {
                secondLargest = largest; // current largest becomes second largest
                largest = arr[i]; // update largest to current element
            } 
            
            // if current element is greater than second largest and not equal to largest
            else if (arr[i] > secondLargest && arr[i] != largest) {
                secondLargest = arr[i]; // update second largest to current element
            }
        }
        
        // Print second largest element and number of comparisons
        System.out.println("Second largest element: " + secondLargest);
        System.out.println("Number of comparisons: " + cmpCount);
    }
}

Credit:

Question 19 In an unsorted list of numbers of size n, if all the elements of the array are sorted then find the element, which lie at the index n/2

Without Comments

public class Q19 {
    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int n = arr.length;
        
        int middleIndex = n / 2;
        
        int middleElement = arr[middleIndex];
        
        System.out.println("Middle element: " + middleElement);
    }
}

With comments

public class Q19 {
    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int n = arr.length;
        
        // calculate index of middle element
        int middleIndex = n / 2;
        
        // get middle element
        int middleElement = arr[middleIndex];
        
        // Print middle element
        System.out.println("Middle element: " + middleElement);
    }
}

Credit:

Question 20 A bitonic list comprises of an increasing sequence of integers immediately followed by a decreasing sequence of integers. Find an element in a bitonic list

Without Comments

public class BitonicSearch {
    public static void main(String[] args) {
        int[] arr = { 1, 3, 6, 9, 12, 15, 14, 11, 8, 5, 2 };
        int n = arr.length;
        int key = 8;
        int index = bitonicSearch(arr, n, key);
        if (index == -1) {
            System.out.println("Element not found");
        } else {
            System.out.println("Element found at index: " + index);
        }
    }

    static int bitonicSearch(int[] arr, int n, int key) {
        int peakIndex = findPeak(arr, n);
        int index = binarySearch(arr, 0, peakIndex, key);
        if (index != -1) { 
            return index;
        }
        return binarySearch(arr, peakIndex + 1, n - 1, key);
    }

    static int findPeak(int[] arr, int n) {
        int low = 0, high = n - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (arr[mid] > arr[mid + 1]) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    static int binarySearch(int[] arr, int low, int high, int key) {
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == key) {
                return mid;
            } else if (arr[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
}

With comments

public class BitonicSearch {
    public static void main(String[] args) {
        int[] arr = { 1, 3, 6, 9, 12, 15, 14, 11, 8, 5, 2 };
        int n = arr.length;
        int key = 8;
        int index = bitonicSearch(arr, n, key);
        if (index == -1) {
            System.out.println("Element not found");
        } else {
            System.out.println("Element found at index: " + index);
        }
    }

    // performs bitonic search on the given array for the given key
    static int bitonicSearch(int[] arr, int n, int key) {
        int peakIndex = findPeak(arr, n); // find the index of the peak element
        int index = binarySearch(arr, 0, peakIndex, key); // perform binary search on the increasing half
        if (index != -1) { 
            return index; // if key is found in increasing half, return its index
        }
        return binarySearch(arr, peakIndex + 1, n - 1, key); // otherwise perform binary search on the decreasing half
    }

    // finds the index of the peak element in the bitonic array
    static int findPeak(int[] arr, int n) {
        int low = 0, high = n - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (arr[mid] > arr[mid + 1]) { // if mid is greater than its next element, search in left half
                high = mid;
            } else { // otherwise, search in right half
                low = mid + 1;
            }
        }
        return low; // returns index of the peak element
    }

    // performs binary search on the given subarray for the given key
    static int binarySearch(int[] arr, int low, int high, int key) {
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == key) { // if key is found at mid index, return its index
                return mid;
            } else if (arr[mid] > key) { // if key is smaller than mid element, search in left half
                high = mid - 1;
            } else { // otherwise, search in right half
                low = mid + 1;
            }
        }
        return -1; // if key is not found, return -1
    }
}

Credit: