Smallest Index With Equal Value in Java
The Smallest Index With Equal Value problem involves finding the smallest index in an array where the value at that index is equal to the index itself. In other words, given an array of integers, the task is to find the index i such that array[i] = i mod 10. If there are multiple such indices, the task is to find the smallest one. If there is no such index, the result is typically indicated by returning -1.
Here's an example:
Example: [Unsorted and Sorted Array]
Input: [3, 5, 6, 9]
Output: Smallest index with equal value in sorted array: -1
Explanation:
Index 0: 0 mod 10 is not equal to 3.
Index 1: 1 mod 10 is not equal to 5.
Index 2: 2 mod 10 is not equal to 6.
Index 3: 3 mod 10 is not equal to 9.
Since the condition is not met at any index it returns -1.
Brute Force Approach
Algorithm
Step 1: Start with the first element of the sorted array.
Step 2: Iterate through each element of the array.
Step 3: For each element, compare its value with its index.
Step 4: If the value at the current index matches the index itself, return the index.
Step 5: If no such index is found after iterating through all elements, return -1 to indicate that no index with equal value was found.
FileName: SmallestIndexWithEqualValue.java
public class SmallestIndexWithEqualValue { // Linear Search for sorted array public static int linearSearchSorted(int[] arr) { for (int i = 0; i < arr.length; i++) { if (arr[i] == (i % 10)) { return i; } } return -1; } public static void main(String[] args) { int[] sortedArray = {3, 5, 6, 9}; // Using linear search for sorted array int index = linearSearchSorted(sortedArray); System.out.println("Smallest index with equal value in sorted array: " + index); } }
Output:
Smallest index with equal value in sorted array: -1
Complexity Analysis: The time complexity is O(n), where n is the size of the array. It has a space complexity of O(1) since it uses only a constant amount of extra space for variables.
Binary Search Approach
Algorithm
Step 1: Initialize two pointers representing the start and end indices of the array.
Step 2: While the first pointer is less than or equal to the second pointer, continue the loop.
Step 3: Inside the loop, calculate the middle index of the array.
Step 4: Check if the value at the middle index is equal to the index itself.
Step 5: If the value is less than the index, update the first pointer.
Step 6: If the value is greater than the index, update the second pointer.
Step 7: Repeat steps 3-6 until the loop condition is no longer satisfied.
Step 8: If the loop exits without finding any matching index, return -1.
FileName: SmallestIndexWithEqualValue1.java
public class SmallestIndexWithEqualValue1 { // Binary Search for sorted array public static int binarySearch(int[] arr) { int left = 0; int right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == (mid % 10)) { return mid; } else if (arr[mid] < mid) { left = mid + 1; } else { right = mid - 1; } } return -1; } public static void main(String[] args) { int[] sortedArray = {3, 5, 6, 9}; // Using binary search for sorted array int index = binarySearch(sortedArray); System.out.println("Smallest index with equal value in sorted array: " + index); } }
Output:
Smallest index with equal value in sorted array: -1
Complexity Analysis: The code has a time complexity of O(log n) and a space complexity of O(1), where n is the size of the array.
HashMap Approach
Algorithm
Step 1: Initialize a HashMap to store value-index pairs.
Step 2: Iterate through the sorted array, storing each element's value and index in the HashMap.
Step 3: Iterate through the array, checking if the HashMap contains a key equal to the index, and if the corresponding value equals the index.
Step 4: Return the index if found; otherwise, return -1.
FileName: SmallestIndexWithEqualValue2.java
import java.util.HashMap; import java.util.Map; public class SmallestIndexWithEqualValue2 { // Hashing for sorted array public static int hashing(int[] arr) { Mapmap = new HashMap<>(); for (int i = 0; i < arr.length; i++) { map.put(arr[i], i); } for (int i = 0; i < arr.length; i++) { if (map.containsKey(i) && map.get(i) == (i % 10)) { return i; } } return -1; } public static void main(String[] args) { int[] sortedArray = {3, 5, 6, 9}; // Using hashing for sorted array int index = hashing(sortedArray); System.out.println("Smallest index with equal value in sorted array: " + index); } }
Output:
Smallest index with equal value in sorted array: -1
Complexity Analysis: The code has a time complexity of O(n) for building the hash map and O(1) for each lookup, resulting in an overall time complexity of O(n). It has a space complexity of O(n) to store the values and indices in the hash map.