Problem Solving

/******************************************************************************

                                Array Insert

*******************************************************************************/

import java.io.*;
import java.lang.*;
import java.util.*;

public class Main {

    // Function to insert x in arr at position pos
    public static int[] insertX(int n, int arr[], int x, int pos) {

        int i;

        // create a new array of size n+1
        int newarr[] = new int[n + 1];

        // insert the elements from
        // the old array into the new array
        // insert all elements till pos
        // then insert x at pos
        // then insert rest of the elements
        for (i = 0; i < n + 1; i++) {
            if (i < pos - 1)
                newarr[i] = arr[i];
            else if (i == pos - 1)
                newarr[i] = x;
            else
                newarr[i] = arr[i - 1];
        }
        return newarr;
    }

    // Driver code
    public static void main(String[] args) {

        int n = 10;
        int i;

        // initial array of size 10
        int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        // print the original array
        System.out.println("Initial Array:\n" + Arrays.toString(arr));

        // element to be inserted
        int x = 50;

        // position at which element
        // is to be inserted
        int pos = 5;

        // call the method to insert x
        // in arr at position pos
        arr = insertX(n, arr, x, pos);

        // print the updated array
        System.out.println("\nArray with " + x
                           + " inserted at position "
                           + pos + ":\n"
                           + Arrays.toString(arr));
    }
}

/******************************************************************************

                                Binary Search

*******************************************************************************/

// Java implementation of recursive Binary Search
public class Main {

    // Returns index of x if it is present in arr[l..
    // r], else return -1
    static int binarySearch(int arr[], int n, int x)
    {
        int left = 0;
        int right = n - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            // If the element is present at the
            // middle itself
            if (arr[mid] == x)
                return mid;

            if (arr[mid] < x) {
                left  = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // We reach here when element is not present
        // in array
        return -1;
    }

    // Driver method to test above
    public static void main(String args[]) {

        int arr[] = { 2, 3, 4, 10, 40 };
        int n = arr.length;
        int x = 10;
        int result = binarySearch(arr, n, x);
        if (result == -1)
            System.out.println("Element not present");
        else
            System.out.println("Element found at index: " + result);
    }
}

/******************************************************************************

                            Remove Duplicate Elements

*******************************************************************************/

// Method 1
import java.util.HashMap;

class Main {

    static void removeDups(int[] a, int n) {

        // Hash map which will store the
        // elements which has appeared previously.
        HashMap<Integer, Boolean> mp = new HashMap<>();

        for (int i = 0; i < n; ++i) {

            // Print the element if it is not
            // present there in the hash map
            // and Insert the element in the hash map
            if (mp.get(a[i]) == null)
            {
                System.out.print(a[i] + " ");
                mp.put(a[i], true);
            }
        }
    }

    // Driver Code
    public static void main(String[] args) {

        int[] arr = { 1, 2, 5, 1, 7, 2, 4, 2 };

        int n = arr.length;
        removeDups(arr, n);
    }
}

// Method 2
public class Main {
    public static int removeDuplicates(int a[], int n)
    {
        // if(array size if 0 or 1 array is already sorted)
        if (n == 0 || n == 1) {
            return n;
        }

        int j = 0;

        // check if the ith element is not equal to
        // the (i+1)th element, then add that element
        // at the jth index in the same array
        // which indicates that te particular element
        // will only be added once in the array
        for (int i = 0; i < n - 1; i++) {
            if (a[i] != a[i + 1]) {
                a[j++] = a[i];
            }
        }

        a[j++] = a[n - 1];

        return j;
    }

    public static void main(String[] args)
    {
        int a[] = { 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6 };

        int n = a.length;

        int j=0;

        // the function will modify the array a[]
        // such that the starting j elements
        // will be having all unique elements
        // and no element will be appearing more than
        // once
        j = removeDuplicates(a, n);

        // printing array elements
        for (int i = 0; i < j; i++)
            System.out.print(a[i] + " ");
    }
}

/******************************************************************************

                                Find Duplicates

*******************************************************************************/

// Method 1
class FindDuplicate {
    // Function to print duplicates
    void printRepeating(int arr[], int size)
    {
        int i;
        System.out.println("The repeating elements are : ");

        for (i = 0; i < size; i++) {
            int j = Math.abs(arr[i]);
            if (arr[j] >= 0)
                arr[j] = -arr[j];
            else
                System.out.print(j + " ");
        }
    }

    // Driver code
    public static void main(String[] args)
    {
        FindDuplicate duplicate = new FindDuplicate();
        int arr[] = { 1, 2, 3, 1, 3, 6, 6 };
        int arr_size = arr.length;

        duplicate.printRepeating(arr, arr_size);
    }
}

/******************************************************************************

                                Find Two Sum

*******************************************************************************/

import java.util.*;

public class Main {

    // Time complexity: O(n)
    private static int[] findTwoSum(int[] nums, int target) {

        Map<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {
                return new int[] { numMap.get(complement), i };
            } else {
                numMap.put(nums[i], i);
            }
        }
        return new int[] {};
    }

    public static void main(String[] args) {

        int[] nums = {2, 7, 11, 15};
        int target = 9;

        int[] sum = findTwoSum(nums, target);

        // Printing The array elements
        for (int i = 0; i < sum.length; i++)
            System.out.print(sum[i] + " ");
    }
}