Question

Problem 1 You are given an array A of integers and an integer k. Implement an algorithm that determines, in linear time, the smallest integer that appears at least k times in A. Problem 2 You are given an array A of integers and an integer k. Implement an algorithm that determines in linear time whether there are two distinct indices i and j in the array such that A[i] = A[j] and the difference between i and j is at most k. The algorithm should use a hash table and return i and j. You can assume that such a pair always exists in A.

Coded in Java. Also advised to use class java.util.HashMap

Answer 1

Problem 1:

Algorithm:

findKthrepeated(int[] arr, int k)

Step 1: Create an empty HashMap

Step 2: Store the elements of array into the HashMap as keys and their frequencies as values

Step 3: Traverse through the map and find the key which the at least k value

Code:

import java.util.HashMap;

public class Algorithm {
    public static void main(String[] args) {

        int[] arr = {1, 2, 3, 4, 2, 2, 5, 6, 3, 2, 7};
        System.out.println(findKthrepeated(arr, 3));

    }

    //Function to find the element which exists k times
    public static int findKthrepeated(int[] arr, int k) {
        int ans = -1;
        //Create a new HashMap which can store Integer type keys and values
        HashMap<Integer, Integer> map = new HashMap<>();

        //Store the elements of array with their respective frequency in the HashMap
        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        }

        //Traverse the map and find the element(key) which has the frequency greater than equal to K
        for (int key : map.keySet()) {
            if (map.get(key) >= k) {
                ans = key;
                return ans;
            }
        }
        return ans;
    }
}

import java.util.HashMap: public class Algorithm { public static void main(String[] args) { int[] arr = · {1, 2, 3, 4, 2, 2, 5, 6, 3, 2, 7}; System.out.println(find(threpeated(arr, k 3)); //Function to find the element which exists at least k times public static int findKthrepeated (int[] arr, int k) { int ans = -1; //Create a new HashMap which can store Integer type keys and values HashMap<Integer, Integer> map = new HashMap<>(); //Store the elements of array with their respective frequency in the HashMap for (int i = 0; i < arr.length; i++) { map.put(arr[i], map.getOrDefault(arr[i], defaultValue: 0) + 1); } IT ans //Traverse the map and find the element(key) which has the frequency greater than equal to K for (int key : map.keySet()) { if (map.get(key) >= k) { key; return ans } } return ans; melange

Output: We get the output 2 as its frequency is greater than k, which is 3.

2 Process finished with exit code o

Problem 2:

Algorithm:

 minDiffenceIndices(int[] A, int k)

Step 1: Create a HashTable

Step 2: Traverse the array and check if the Hash Table already contains the current element.

Step 3: if yes, then check if the difference between the current index of the element minus the previous index is less than equal to k, If yes print the current and previous index and return.

Step 4: Else keep on storing the array element with its current position.

Code:

import java.util.Hashtable;

public class Algorithm {
    public static void main(String[] args) {

        int[] arr = {1, 2, 3, 4, 2, 2, 5, 6, 3, 2, 7};
        minDiffenceIndices(arr, 6);

    }

    //Function to find the indices i and j such that A{i] = A[j] and j - i <= k
    public static void minDiffenceIndices(int[] A, int k) {
        int[] ans = {-1, -1};

        //Create a HashTable which can store Integer type keys and values
        Hashtable<Integer, Integer> map = new Hashtable<>();

        //Traverse the array
        for (int i = 0; i < A.length; i++) {

            //Check if an element is already stored as a key in the table
            if (map.containsKey(A[i])) {

                // If yes then check if the difference between the current index of the element
                // and the previous index is less than equal to k
                if (i - map.get(A[i]) <= k) {
                    ans[0] = map.get(A[i]);
                    ans[1] = i;
                    System.out.println(ans[0] + " " + ans[1]);
                    return;
                }
            }

            //Store the element with its current index in the hash table
            map.put(A[i], i);
        }
    }
}


import java.util.Hashtable; public class Algorithm { public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 2, 2, 5, 6, 3, 2, 7}; mindiffenceIndices(arr, k 6); } // Function to find the indices i and j such that A{i] A[j] and j - i <= k public static void minDiffenceIndices (int[] a, int k) { int[] ans = {-1, -1}; //Create a HashTable which can store Integer type keys and values Hashtable<Integer, Integer> map = new Hashtable<>(); //Traverse the array for (int i = 0; i < A.length; i++) { //Check if an element is already stored as a key in the table if (map.containskey (A[i])) { // If yes then check if the difference between the current index of the element // and the previous index is less than equal to k if (i - map.get(A[i]) <= k) { ans[@] map.get(A[i]); ans[1] = i; System.out.println(ans [@] + + ans[1]); return; } ههه //Store the element with its current index in the hash table map.put(A[i], i); } } }

Output: We get the ouput 1 and 4 as 2 is present at 1 and 4 and K is equal to 6

14 Process finished with exit code @ —

Note: Both HashMap and HashTable can be used to solve the two problems, as both the data structures work in a similar way.