Searching DSA

➤ Java Bean with Examples
➤ How to Code a Game
➤ Array Programs in Java
➤ Java Inline Thread Creation
➤ Java Custom Exception
➤ Hibernate vs JDBC
➤ Object Relational Mapping
➤ Check Oracle DB Size
➤ Check Oracle DB Version
➤ Generation of Computers
➤ XML Pros & Cons
➤ Git Analytics & Its Uses
➤ Top Skills for Cloud Professional
➤ How to Hire Best Candidates
➤ Scrum Master Roles & Work
➤ CyberSecurity in Python
➤ Protect from Cyber-Attack
➤ Solve App Development Challenges
➤ Top Chrome Extensions for Twitch Users
➤ Mistakes That Can Ruin Your Test Metric Program

Searching DSA | We will discuss the following algorithms: linear search, Binary search, Unbounded Binary Search, and Floyd’s Tortoise and Hare Algorithm.

Table of Contents

Linear Search is a straightforward search algorithm that checks each element in a list sequentially until the target element is found or the list is exhausted.

Given an array of elements and a target value, find the index of the target value in the array. If the target value is not found, return -1.

Example:-
Array: [10, 20, 30, 40, 50]
Item to search: 30
Output: 2

class LinearSearch {
    // perform linear search
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        int target = 30;
        int result = linearSearch(arr, target);

        if (result == -1) {
            System.out.println("Element not present");
        } else {
            System.out.println("Element found at index " + result);
        }
    }
}

Time complexity O(n) and auxiliary space O(1). We can reduce the iteration to half and check for target element from both the start and end index:-

// Perform linear search
public static int linearSearch(int[] arr, int target) {
    for (int i = 0, j = arr.length - 1; i <= j; i++, j--) {
        if (arr[i] == target) {
            return i;
        } else if (arr[j] == target) {
            return j;
        }
    }
    return -1; // Target not found
}

Time complexity O(n/2) = O(n) and auxiliary space O(1).

Binary Search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the portion of the list that could contain the item in half until you’ve narrowed the possible locations to just one.

Given a sorted array of n elements and a target value, find the index of the target value in the array. If the target value is not found in the array, return -1. In case of multiple occurrences return the index of any occurrence.

Examples:

  • Array: [2, 3, 4, 10, 40], Item to search: 10; Output: 3
  • Array: [1, 2, 2, 2, 5], Item to search: 2; Output: 1 (or 2 or 3)
  • Array: [10, 20, 30, 40, 50], Item to search: 25; Output: -1
  • Array: [5, 15, 25, 35, 45], Item to search: 5; Output: 0
  • Array: [8, 16, 24, 32, 40, 40], Item to search: 40; Output: 4 (or 5)

Steps of Binary Search

  1. Initialization: Start with the entire array (i.e., set the low index to 0 and the high index to n-1).
  2. Iteration:
  • While the low index is less than or equal to the high index:
  • Calculate the middle index: mid = low + (high – low) / 2.
  • Compare the target value with the middle element of the array.
  • If the target value is equal to the middle element, return the middle index.
  • If the target value is less than the middle element, search the left half by setting high = mid – 1.
  • If the target value exceeds the middle element, search the right half by setting low = mid + 1.
  1. Completion: If the low index exceeds the high index, return -1 (indicating the target value is not in the array).
public class Test {
    public static void main(String[] args) {
        int[] array = { 2, 3, 4, 10, 40 };
        int item = 10;
        System.out.println(binarySearch(array, item));
    }

    private static int binarySearch(int[] array, int target) {
        int low = 0;
        int high = array.length - 1;

        while (high >= low) {
            int mid = low + (high - low) / 2;

            // Check if target is present at mid
            if (array[mid] == target) {
                return mid;
            }

            // If target is smaller, ignore the right half
            if (array[mid] > target) {
                high = mid - 1;
            }

            // If target is greater, ignore the left half
            else {
                low = mid + 1;
            }
        }

        // Target is not present in the array
        return -1;
    }
}

Time complexity O(log n) and auxiliary space O(1). To use binary search, the array must be sorted. The high will be the floor(log2 n). Using recursion the same can be done as:-

public class Test {
    public static void main(String[] args) {
        int[] array = { 2, 3, 4, 10, 40 };
        int item = 10;
        System.out.println(binarySearch(array, 0, array.length, item));
    }

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

Recursive Binary Search:

  • Time Complexity: O(log n)
  • Space Complexity: O(log n) due to the recursion stack.

Iterative Binary Search:

  • Time Complexity: O(log n)
  • Space Complexity: O(1) since it doesn’t use the call stack.

The iterative approach is more space-efficient, making it better suited for environments where memory usage is a concern.

The Java Arrays class contains a pre-defined binarySearch() method which uses the iterative approach:-

int[] array = { 2, 3, 4, 10, 40 };
int item = 10;
System.out.println(Arrays.binarySearch(array, item));

3. Index of First Occurrence in a Sorted Array

For a given sorted array (which might contain duplicates), and target element, find the first occurrence of the target element. Consider 0-based indexing.

array = {1, 10, 10, 20, 20, 40}, target = 20. O/P: 3
array = {10, 20, 30}, target = 15. O/P: -1
array = {15, 15, 15}, target = 15. O/P: 0

The naive solution (linear search) is to traverse through the array and return the index if an element is found. If an element is not found, return -1. The time complexity and auxiliary space for this will be O(n) and O(1), respectively.

Let us see how it can be done in O(log n) times. First, we will see the recursive approach and then the iterative approach.

public class Test {
    // recursive 
    public static int firstOcc(int[] arr, int low, int high, int target) {
        if (low > high) {
            return -1;
        }
        int mid = low + (high - low) / 2;

        if (arr[mid] > target) {
            return firstOcc(arr, low, mid - 1, target);
        } else if (arr[mid] < target) {
            return firstOcc(arr, mid + 1, high, target);
        }

        if (mid == 0 || arr[mid - 1] != arr[mid]) {
            return mid;
        } 
        return firstOcc(arr, low, mid - 1, target);
    }

    public static void main(String[] args) {
        int[] arr = { 5, 10, 10, 20, 20, 20 };
        int target = 20;
        int result = firstOcc(arr, 0, arr.length, target);
        System.out.println(result);
    }
}

Iterative Approach:-

public class Test {
    // iterative
    public static int firstOcc(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] > target) {
                high = mid - 1;
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                if (mid == 0 || arr[mid - 1] != target) {
                    return mid;
                }
                high = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = { 5, 10, 10, 20, 20, 20 };
        int target = 20;
        int result = firstOcc(arr, target);
        System.out.println(result);
    }
}

The time complexity for both approaches is O(log n). The auxiliary space for recursive and iterative approaches is O(n) and O(1), respectively.

4. Index of Last Occurrence in a Sorted Array

For a given sorted array (which might contain duplicates), and target element, find the last occurrence of the target element. Consider 0-based indexing.

array = {1, 10, 10, 20, 20, 40}, target = 20. O/P: 4
array = {10, 20, 30}, target = 15. O/P: -1
array = {15, 15, 15}, target = 15. O/P: 3

public class Test {
    // iterative
    public static int lastOcc(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] > target) {
                high = mid - 1;
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                if (mid == arr.length - 1 || arr[mid + 1] != arr[mid]) {
                    return mid;
                }
                low = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = { 5, 10, 10, 20, 20, 40 };
        int target = 20;
        int result = lastOcc(arr, target);
        System.out.println(result);
    }
}

5. Count Occurrence in a Sorted Array

Array = {10, 20, 20, 20, 30, 30}, target= 20; O/P: 3
Array = {10, 10, 10, 10, 10}, target= 10; O/P: 5
Array = {5, 8, 10}, target= 7; O/P: 0
Problem: 34


public class Test {
    // iterative
    public static int countOcc(int[] arr, int target) {
        int first = firstOcc(arr, target);
        if (first == -1) {
            return 0;
        }
        return lastOcc(arr, target, first) - first + 1;
    }

    public static int lastOcc(int[] arr, int target, int low) {
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] > target) {
                high = mid - 1;
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                if (mid == arr.length - 1 || arr[mid + 1] != arr[mid]) {
                    return mid;
                }
                low = mid + 1;
            }
        }
        return -1;
    }

    public static int firstOcc(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] > target) {
                high = mid - 1;
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                if (mid == 0 || arr[mid - 1] != arr[mid]) {
                    return mid;
                }
                high = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = { 5, 10, 10, 20, 20, 40 };
        int target = 20;
        int result = countOcc(arr, target);
        System.out.println(result);
    }
}

With this approach, we can do this in O(log n) time and O(1) auxiliary space.

6. Majority Element in Sorted Array

An element in a given array is called majority if it exists more than n/2 times, where n is the length of the array. Problem: 1150

I/P: arr = {3, 4, 8, 8, 8}; O/P: Any index of 8
I/P: arr = {3, 4, 5, 7, 7, 7}; O/P: No majority (-1)
I/P: arr = {20, 30, 40, 50, 50, 50, 50}; O/P: Any index of 50

We have discussed this for unsorted arrays in the Boyer-Moore Voting Algorithm which ensures O(n) time complexity and O(1) space complexity. Let us see how it can be done for the sorted array in O(log n) times:-

  • Middle Index: Given that the majority element appears more than half the time, it must be present at the middle index of the array. This is a key observation.
  • Binary Search: Since the array is sorted, binary search can be used to efficiently find the first and last occurrences of the majority element, which operates in O(log n) time.
  • Verification: Once identified, counting the occurrences from the middle index and verifying if the count is greater than n/2 will confirm if it is the majority element.

Binary search for the first occurrence: O(log n)
Binary search for the last occurrence: O(log n)
Total time complexity: O(log n)
Auxiliary Space: O(1)

public class Test {
    public static void main(String[] args) {
        int[] arr = { 20, 30, 40, 50, 50, 50, 50 };
        System.out.println(majorityElementIndex(arr)); // 3
    }

    // majority element must be available at middle
    private static int majorityElementIndex(int[] arr) {
        int n = arr.length, mid = n / 2, majorityEle = arr[mid];
        int firstOcc = firstIndex(arr, majorityEle, mid);

        // expected last occurrence
        int lastOcc = firstOcc + n / 2;

        // verify if it is a majority element
        if (lastOcc < n - 1 && arr[lastOcc] == majorityEle) {
            return mid;
        }
        return -1;
    }

    private static int firstIndex(int[] arr, int target, int high) {
        int low = 0;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] > target) {
                low = mid + 1;
            } else {
                high = mid; // include mid element
            }
        }
        return low;
    }
}

7. Count 1’s in a Sorted Binary Array

array = {0, 0, 0, 1, 1, 1, 1}; Count = 4
array = {1, 1, 1, 1, 1, 1, 1}; Count = 7
array = {0, 0, 0, 0, 0, 0, 0}; Count = 0

In a binary array, there are only 2 possible elements:- 0 or 1. We have to find the last occurrence of 0. Problem

  • If the middle element is 0 then check in the right part of the array.
  • Else check whether it is index == 0 or the left adjacent element is 0. If yes, then it is the last index of 0, and return length - mid index. The length – mid gives the count of 1.
  • Otherwise, check in the left part of the array.
public class Test {
    public static void main(String[] args) {
        int[] arr = { 0, 0, 0, 0, 1, 1, 1 };
        int result = countOcc(arr);
        System.out.println(result);
    }

    private static int countOcc(int[] arr) {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == 0) {
                low = mid + 1;
            } else {
                if (mid == 0 || arr[mid - 1] == 0) {
                    return arr.length - mid;
                }
                high = mid - 1;
            }
        }
        return 0;
    }
}

8. Square Root of a number

For a given number N, if N is a perfect square then return its square root, else return the floor of the square root. Don’t use any pre-defined method/function. Problem: 69. Examples:-

N = 4; O/P: 2
N = 14; O/P: 3
N = 25; O/P: 5

// naive solution
public class Test {
    private static int sqrt(int n) {
        int i = 1;
        while (i * i <= n) {
            i++;
        }
        return i - 1;
    }

    public static void main(String[] args) {
        System.out.println(sqrt(15));
    }
}

Time complexity O(sqrt(n)) and auxiliary space O(1). We can do this in O(log n) time using the binary search algorithm.

For numbers greater than or equal to 4, the square root will always be less than or equal to n / 2. Therefore use high = n/2.

public class Test {
    public static void main(String[] args) {
        System.out.println(sqrt(15));
    }

    private static int sqrt(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        int low = 1, high = n / 2, res=-1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (mid * mid == n) {
                return mid;
            } else if (mid * mid > n) {
                high = mid - 1;
            } else {
                low = mid + 1;
                res = mid;
            }
        }
        return res;
    }
}

The algorithm narrows down the potential square root value by repeatedly dividing the search range in half, efficiently finding the floor value with a time complexity of O(log n). This approach is both fast and accurate, ensuring that you find the largest integer x such that x^2 is less than or equal to n

9. Unbounded Binary Search (Search in an Infinite Sorted Array)

Array = {1, 10,15, 20, 40, 80, 90, 100, 120, 500, …}, X = 100; O/P: 7
Array = {20, 40, 100, 300, …}, X = 50; O/P: -1

An infinite array means we can’t use the length variable of the array. We have to find a solution without using the array.length property.

public class Test {
    // naive solution
    private static int search(int[] arr, int x) {
        int i = 0;
        while (true) {
            if (arr[i] == x) {
                return i;
            }
            if (arr[i] > x) {
                return -1;
            }
            i++;
        }
    }

    public static void main(String[] args) {
        int[] arr = { 1, 10, 15, 20, 40, 80, 90, 100, 120, 500 };
        System.out.println(search(arr, 40));
    }
}

It has time complexity O(position) and auxiliary space O(1). We can also do this in O(log position) times. The idea for this is to begin from index 1, then go to index 2, 4, 8, 16, and so on. Keep doing this while the current element (index i) is smaller than x. Once the current element becomes greater than or equal to x then the element must be present in the left side only. Now consider element from index (i)/2 + 1 to i -1 and apply binary search.

public class Test {
    private static int search(int[] arr, int x) {
        if (arr[0] == x) {
            return 0;
        }
        int i = 1;
        while (arr[i] < x) {
            i = i * 2;
        }
        if (arr[i] == x) {
            return i;
        }
        return binarySearch(arr, (i / 2) +1, i-1, x);
    }

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

    public static void main(String[] args) {
        int[] arr = { 1, 10, 15, 20, 40, 80, 90, 100, 120, 500 };
        System.out.println(search(arr, 40)); // 4
    }
}

Time complexity O(log (position) + log (position)) = O(log (position)). This algorithm is commonly known as Unbounded Binary Search.

10. Search in a sorted Rotated Array

Consider it as a distinct array that doesn’t contain any duplicates. Problem Link: 33

Array = {10, 20, 30, 40, 50, 8, 9}, x = 30; O/P: 2
Array = {100, 200, 300, 10, 20}, x = 40; O/P: -1

A naive solution can be a linear search and it will have time complexity O(n) and auxiliary space O(1). We can also do this in O(log n) time using binary search.

In the sorted rotated array, from the middle index, one half will be always sorted. Compare the middle element with the corner elements. If the arr[low] < arr[mid] then the left half is sorted, else right half is sorted.

If the left half (arr[low] to arr[mid]) is sorted: Check range:-

  • If the target element x is within the range (arr[low] <= x < arr[mid]), update high to mid - 1 to search in the left half.
  • Otherwise, update low to mid + 1 to search in the right half.

If the right half (arr[mid] to arr[high]) is sorted: Check range:-

  • If the target element x is within the range (arr[mid] < x <= arr[high]), update low to mid + 1 to search in the right half.
  • Otherwise, update high to mid - 1 to search in the left half.
public class Test {
    public static void main(String[] args) {
        int[] arr = { 10, 20, 40, 60, 5, 8 };
        System.out.println(binarySearch(arr, 40)); // 2
    }

    private static int binarySearch(int[] arr, int x) {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == x) {
                return mid;
            }
            // left half is sorted
            if (arr[low] <= arr[mid]) {
                // check element present in this part?
                if (x >= arr[low] && x < arr[mid]) {
                    high = mid - 1; // yes => check in left half
                } else {
                    low = mid + 1; // no => right half
                }
            }
            // right half is sorted
            else {
                // check element present in this part?
                if (x > arr[mid] && x <= arr[high]) {
                    low = mid + 1; // yes => check in right half
                } else {
                    high = mid - 1; // no => left half
                }
            }
        }
        return -1;
    }
}

Search in a sorted Rotated Array With Duplicate Elements

Same problem as Search in a sorted Rotated Array but the array may contain duplicate elements:- 81. Solution

Given the array nums after the rotation and an integer target, return true if the target is in nums, or false if it is not in nums. You must decrease the overall operation steps as much as possible.

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

class Solution {
    public boolean search(int[] nums, int target) {
        int l = 0, h = nums.length - 1;
        while (l <= h) {
            int mid = l+ (h - l) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[l] == nums[mid] && nums[mid] == nums[h]) {
                l = l + 1;
                h = h - 1;
                continue;
            }
            // left half is sorted
            if (nums[l] <= nums[mid]) {
                if (nums[l] <= target && nums[mid] > target) {
                    h = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            // right half is sorted
            else {
                if (nums[mid] < target && nums[h] >= target) {
                    l = mid + 1;
                } else {
                    h = mid - 1;
                }
            }
        }
        return false;
    }
}

11. Find Peak Elements in an unsorted Array

Peak element means not smaller than its neighbors or the element is greater/equal than its right and left elements. For a given unsorted array, return one of its peak elements. Problem: 162

Array = {5, 10, 20, 15, 7} Peak element = 20 (because it is greater than its neighbors).
Array = {10, 20, 15, 5, 23, 90, 67} Peak elements = 20, 90
Array = {80, 70, 60} Peak element = 80
Array = {80, 70, 90} Peak elements = 80, 90

For the first element, we have to check only the right side (1st index), and for the last element, we have to check only the left side (n-1 index).

// naive solution
public class Test {
    public static void main(String[] args) {
        int[] arr = { 5, 10, 20, 15, 7 };
        System.out.println(peakElement(arr)); // 20
    }

    private static int peakElement(int[] arr) {
        int n = arr.length;
        if (n == 1) return arr[0];
        if (arr[0] >= arr[1]) return arr[0]; // first element
        if (arr[n - 1] >= arr[n - 2]) return arr[n - 1]; // last element
        for (int i = 1; i < n - 1; i++) {
            if (arr[i - 1] <= arr[i] && arr[i] >= arr[i + 1]) {
                return arr[i];
            }
        }
        return -1;
    }
}

Time complexity O(n) and space complexity O(1). We can do this in O(log n) using binary search. This is an example of one of those problems where we can apply the binary search algorithm even though the array is not sorted.

Go to the mid element and check whether it is a peak element or not. How to decide where to go after that left side or right side? If the left element is greater than the mid element then go to the left part else go to the right side.

public class Test {
    public static void main(String[] args) {
        int[] arr = { 5, 10, 20, 15, 7 };
        System.out.println(peakElement(arr)); // 20
    }

    // naive solution
    private static int peakElement(int[] arr) {
        int low = 0, n = arr.length, high = n - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            // leftmost & rightmost element & peak
            if ((mid == 0 || arr[mid - 1] <= arr[mid]) && 
                (mid == n - 1) || arr[mid + 1] <= arr[mid]) {
                return arr[mid];
            }
            if (mid > 0 && arr[mid - 1] >= arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
}

Time complexity O(log n) and space complexity O(1).

12. Two Pointer Approach

a. Find Pair Sum in Unsorted Array

Given an unsorted array and a number x, we need to find if there is a pair in the array with a sum equal to x or not. We can use Hashing to solve this problem:- Pair with the given Sum in an unsorted array

If you want to return the index of the pairs then we can use HashMap where the key is arr[i] and the value is i. Check the solution here:- Two Sum with Hash Map

Using hashing is the best approach for unsorted arrays, but if the array is sorted then the two-pointer approach is most suitable.

b. Find Sum Pair in Sorted Array

Given a sorted array and a number x, we need to find if there is a pair in the array with a sum equal to x or not. Problem: 167

Array = {2,5,8,12,30}, x=17; O/P: Yes (5,12)
Array = {3,8,13,18}, x=14; O/P: No
Array = {2,4,8,9,11,12,20,30}, x=23; O/P: Yes (11, 12)

Two pointer approach steps:-

  • Start with one pointer at the beginning (left) and one at the end (right).
  • Adjust pointers based on your condition. For example, if checking for a sum:-
    • If (arr[left] + arr[right]) > sum then Move the right pointer towards the left.
    • If (arr[left] + arr[right]) < sum then Move the left pointer towards the right.
  • Continue until the pointers are met or the condition is satisfied.
public class Test {
    public static void main(String[] args) {
        int[] arr = { 2, 5, 8, 12, 30 };
        int sum = 17;
        System.out.println(isPair(arr, sum)); // true
    }

    private static boolean isPair(int[] arr, int sum) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int currentSum = arr[left] + arr[right];
            if (currentSum > sum) {
                right--;
            } else if (currentSum < sum) {
                left++;
            } else {
                return true;
            }
        }
        return false;
    }
}

Time complexity O(n).

c. Find Triplet Sum Pair in Sorted Array

Given a sorted array and a sum, find if there is a triplet with the given sum. Example:- array = {2,3,4,8,9,20,40}, x=32; O/P: Yes (4, 8, 20}.

The naive solution could be to run three loops with variables starting from i=0, j=i+1, k=j+1 till i<n, j<n, k<n, and compare arr[i] + arr[j] + arr[k] == sum or not. The time complexity for this will be O(n^3).

To optimize it to O(n^2). We can use the two-pointer approach and the previous program to find the triplet. The solution is to run the isPair() method for every index. Fix every element as the first index and call the isPair() method for index i+1 to n-1 and for the sum x-arr[i]. This time the isPair() method parameters will be slightly different.

public class Test {
    public static void main(String[] args) {
        int[] arr = { 2, 3, 4, 8, 9, 20, 40 };
        int sum = 32;
        System.out.println(hasTriplet(arr, sum)); // true
    }

    private static boolean hasTriplet(int[] arr, int sum) {
        for (int i = 0; i < arr.length; i++) {
            if (isPair(arr, i + 1, arr.length - 1, sum - arr[i])) {
                return true;
            }
        }
        return false;
    }

    private static boolean isPair(int[] arr, int left, int right, int sum) {
        while (left < right) {
            int currentSum = arr[left] + arr[right];
            if (currentSum > sum) {
                right--;
            } else if (currentSum < sum) {
                left++;
            } else {
                return true;
            }
        }
        return false;
    }
}

Time complexity O(n^2).

d. Find Triplet Sum Pair in Unsorted Array

In the previous example, we have seen that finding a triplet sum pair in a sorted array is O(n^2) whereas sorting requires O(n log n) hence if we first sort the array and then apply hasTriplet() then overall time complexity will remain O(n^2). Therefore to solve this problem first sort the array, and then apply the hasTriplet() method. Problem: 15

public class Test {
    public static void main(String[] args) {
        int[] arr = { 9, 3, 40, 2, 8, 20, 4 };
        int sum = 32;

        // first sort it
        Arrays.sort(arr); // O(n log n)

        System.out.println(hasTriplet(arr, sum)); // true
    }
}

We can also solve it using hashing however the time complexity will be the same O(n^2) but it will take extra auxiliary space O(n).

e. Count/Find Pairs with Given Sum

Unsorted Array

Find the pairs with the given sum in an unsorted array. Example:- Array = { 10, 2, 11, 5, 9, 3, 4, 8 }, sum = 13; Pairs are:- [11, 2], [3, 10], [4, 9], [8, 5]

public class Test {
    public static void main(String[] args) {
        int[] arr = { 10, 2, 11, 5, 9, 3, 4, 8 };
        int sum = 13;
        System.out.println(findPairs(arr, sum)); 
        // [[11, 2], [3, 10], [4, 9], [8, 5]]
    }

    private static List<List<Integer>> findPairs(int[] arr, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        Set<Integer> elements = new HashSet<>();
        for (int num : arr) {
            int complement = sum - num;
            if (elements.contains(complement)) {
                result.add(List.of(num, complement));
            } else {
                elements.add(num);
            }
        }
        return result;
    }
}

Time complexity O(n).

Sorted Array

Find the pairs with the given sum in an sorted array. Example:- Array = { 2, 3, 4, 5, 8, 9, 10, 11 }, sum = 13; Pairs are:- [ [2, 11], [3, 10], [4, 9], [5, 8] ]

public class Test {
    public static void main(String[] args) {
        int[] arr = { 2, 3, 4, 5, 8, 9, 10, 11 };
        int sum = 13;
        System.out.println(findPairs(arr, sum));
        // [[2, 11], [3, 10], [4, 9], [5, 8]]
    }

    private static List<List<Integer>> findPairs(int[] arr, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int currentSum = arr[left] + arr[right];
            if (currentSum == sum) {
                result.add(List.of(arr[left], arr[right]));
                left++;
                right--;
            } else if (currentSum > sum) {
                right--;
            } else {
                left++;
            }
        }
        return result;
    }
}

f. Count/Find Triplet Pairs with the Given Sum

Given an array and a sum, find all triplets with the given sum. Example:- array = {12, 3, 4, 1, 6, 9, 15, 7, 8}, x=24; Possible Triplets: [[1, 8, 15], [3, 6, 15], [3, 9, 12], [4, 8, 12], [7, 8, 9]]. Problem: 15

In the previous example, we have seen that finding a triplet sum pair in a sorted array is O(n^2) whereas sorting requires O(n log n) hence if we first sort the array and then apply the findTripleParis() along with the previous findPairs() method.

In the 

public class Test {
    public static void main(String[] args) {
        int[] arr = { 10, 3, 9, 4, 6, 1, 7, 8, 12, 14, 15, 16 };
        int sum = 24;
        System.out.println(findTriplePairs(arr, sum));
    }

    private static List<List<Integer>> findTriplePairs(int[] arr, int sum) {
        Arrays.sort(arr);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < arr.length - 2; i++) {
            List<List<Integer>> twoPairs = 
              findDoublePairs(arr, i + 1, arr.length - 1, sum - arr[i]);
            if (!twoPairs.isEmpty()) {
                for (List<Integer> list : twoPairs) {
                    List<Integer> newList = new ArrayList<>(list);
                    newList.add(arr[i]);
                    result.add(newList);
                }
            }
        }
        return result;
    }

    private static List<List<Integer>> findDoublePairs(int[] arr, int left, 
                                                   int right, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        while (left < right) {
            int currentSum = arr[left] + arr[right];
            if (currentSum == sum) {
                result.add(List.of(arr[left], arr[right]));
                left++;
                right--;
            } else if (currentSum > sum) {
                right--;
            } else {
                left++;
            }
        }
        return result;
    }
}

Output:-

[ [7, 16, 1], [8, 15, 1], [9, 14, 1], [6, 15, 3], [7, 14, 3], [9, 12, 3], [6, 14, 4], [8, 12, 4], [8, 10, 6], [8, 9, 7] ]

g. Pythagorean Triplet problem

Find if there is a triplet a, b, c such that a^2 + b^2 = c^2. Example:- Array: {3, 1, 4, 6, 5}; The triplet [3, 4, 5] satisfies the condition 32 + 4 2 = 52. Problem

Steps:-

  • Square all elements.
  • Sort the array to enable the use of the two-pointer technique.
  • Iterate over each element as the potential largest element c of the triplet.
  • For each c, use a hash set to find a and b such that a2 + b2 = c2
public class Test {
    public static void main(String[] args) {
        int[] arr = { 5, 12, 13, 9, 3, 4, 15, 8, 20 };
        System.out.println(pythagoreanTriplet(arr)); 
        // [[15, 12, 9], [13, 12, 5], [5, 4, 3]]
    }

    private static List<List<Integer>> pythagoreanTriplet(int[] arr) {
        List<List<Integer>> result = new ArrayList<>();
        // square all elements
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i] * arr[i];
        }
        // sort the squared array
        Arrays.sort(arr);

        // fix one element and use hashset for the other two
        for (int i = arr.length - 1; i > 1; i--) {
            Set<Integer> set = new HashSet<>();
            int targetSum = arr[i];
            for (int j = 0; j < i; j++) {
                if (set.contains(targetSum - arr[j])) {
                    result.add(List.of((int) Math.sqrt(targetSum), (int) Math.sqrt(arr[j]),
                            (int) Math.sqrt(targetSum - arr[j])));
                }
                set.add(arr[j]);
            }
        }
        return result;
    }
}

Time Complexity: O(n^2)

  • O(n log n) for sorting the array.
  • O(n^2) for iterating over the elements and using the hash set.

Space Complexity: O(n) for the hash set used to store the elements during traversal.

However, since the array is sorted therefore you can also use the two-pointer approach to find the two pairs. Then the program will have O(1) if we ignore storing the result.

// Apply two pointer considering each element as c
for (int i = arr.length - 1; i > 1; i--) {
    int low = 0, high = i - 1;
    while (low < high) {
        int sum = arr[low] + arr[high];
        if (sum == arr[i]) {
            result.add(List.of((int) Math.sqrt(arr[low]), 
                (int) Math.sqrt(arr[high]), (int) Math.sqrt(arr[i])));
            break;
        } else if (sum < arr[i]) {
            low++;
        } else {
            high--;
        }
    }
}

13. Median of Two Sorted Arrays

For the given two sorted arrays, find the median. Problem: 4. Examples:-

a1[ ] = {1, 2, 3, 4, 5, 6}
a2[ ] = {10, 20, 30, 40, 50}
Median = 6 (because merged array: {1, 2, 3, 4, 5, 6, 10, 20, 30, 40, 50};

a1[ ] = {10, 20, 30, 40, 50, 60}
a2[ ] = {1, 2, 3, 4, 5}
Median = 10 (because merged array: {1, 2, 3, 4, 5, 10, 20, 30, 40, 50, 60};

If the merged array length is odd then the median is the middle element, but in the case of array length = even, the median is the average of the middle two elements.

a1[ ] = {10, 20, 30, 40, 50}
a2[ ] = {5, 15, 25, 35, 45}
Median = 27.5 (because merged array: {5, 10, 15, 20, 25, 30, 35, 40, 45, 50})

Naive solution with time complexity O((n1 + n2) * log(n1 + n2)):-

  1. Create an array temp[ ] of size n1 + n2.
  2. Copy both array elements to temp[ ].
  3. Sort temp[ ].
  4. If (n1 + n2) is odd, then return the middle of temp.
  5. Else return the average of the middle two elements.
// naive solution
import java.util.Arrays;
public class Test {
    public static void main(String[] args) {
        int a1[] = { 10, 20, 30, 40, 50 };
        int a2[] = { 5, 15, 25, 35, 45 };
        System.out.println(median(a1, a2)); // 27.0
    }

    private static double median(int[] a1, int[] a2) {
        int tempLength = a1.length + a2.length;
        int[] temp = new int[tempLength];
        System.arraycopy(a1, 0, temp, 0, a1.length);
        System.arraycopy(a2, 0, temp, a1.length, a2.length);
        Arrays.sort(temp);
        System.out.println(Arrays.toString(temp));
        return (tempLength & 1) == 1 ? temp[tempLength / 2] : 
            (double)(temp[tempLength / 2] + temp[(tempLength / 2) - 1]) / 2;
    }
}

Output:-
[5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
27.5

This solution can be optimized to O(log n1) using binary search. In this case, we will always consider n1 <= n2. This approach has a time complexity of O(log(min(n, m))) and auxiliary space of O(1).

Steps:-

  • Start with two sorted arrays, say A and B. Ensure that A is the smaller array to minimize the number of operations.
  • Binary Search on the Smaller Array:-
    • Perform a binary search on the smaller array A. Let’s denote their lengths by n and m respectively.
    • Calculate the partition indices i and j for A and B.
  • Partitioning:-
    • Divide both arrays into left and right parts. Ensure the combined left parts are less than or equal to the combined right parts.
    • Adjust partitions to ensure the condition is met.
  • Check for Median:-
    • If the left parts are valid, find the maximum of the left parts and the minimum of the right parts.
    • If the total length is odd, the median is the maximum of the left parts.
    • If the total length is even, the median is the average of the left parts’ maximum and the right parts’ minimum.
public class Test {
    public static void main(String[] args) {
        int[] arr1 = { 1, 3, 8 };
        int[] arr2 = { 7, 9, 10, 11 };
        double median = findMedianInSortedArrays(arr1, arr2);
        System.out.println("Median is: " + median); // Output: 8.0
    }

    private static double findMedianInSortedArrays(int[] a1, int[] a2) {
        // consider a1.length <= a2.length
        if (a2.length < a1.length) {
            findMedianInSortedArrays(a2, a1);
        }
        int n1 = a1.length, n2 = a2.length, begin = 0, end = n1;

        while (begin <= end) {
            int i1 = begin + (end - begin) / 2;
            int i2 = ((n1 + n2 + 1) / 2) - i1;

            int min1 = i1 == n1 ? Integer.MAX_VALUE : a1[i1];
            int max1 = i1 == 0 ? Integer.MIN_VALUE : a1[i1 - 1];
            int min2 = i2 == n2 ? Integer.MAX_VALUE : a2[i2];
            int max2 = i2 == 0 ? Integer.MIN_VALUE : a2[i2 - 1];

            if (min1 >= max2 && max1 <= min2) {
                if ((n1 + n2) % 2 == 0) {
                    return (Math.max(max1, max2) + Math.min(min1, min2)) / 2;
                }
                return Math.max(max1, max2);
            }

            if (max1 > min2) {
                end = i1 - 1;
            } else {
                begin = i1 + 1;
            }
        }
        throw new IllegalArgumentException("Input arrays are not sorted");
    }
}
  • min1 = Minimum element on the right side of array1.
  • max1 = Maximum element on the left side of array1.
  • min2 = Minimum element on the right side of array2.
  • max2 = Maximum element on the left side of array2.

14. Repeating Element

Identify the repeating element in a given array. Conditions:-

  • Only one element repeats, any number of times.
  • All elements from 0 to max(arr) are present.
  • Therefore, 0 <= max(arr) <= n-2. Array size will be <= n-2.

Examples:-

Array = {0, 2, 1, 3, 2, 2} Output: 2
Array = {1, 2, 3, 0, 3, 4, 5} Output: 3
Array = {0, 0} Output: 0

Our target is to solve this problem in O(n) time, and O(1) auxiliary space and without modifying the array. But let us see the easiest solution first.

Solution with O(n^2) time and O(1) space.

public class Test {
    public static void main(String[] args) {
        int[] arr = { 0, 2, 1, 3, 2, 2 };
        System.out.println(findDuplicate(arr)); // 2
    }

    // O(n^2)
    private static int findDuplicate(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 -1;
    }
}

Solution with O(n log(n)) time and O(1) space.

private static int findDuplicate(int[] arr) {
    Arrays.sort(arr);
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == arr[i + 1]) {
            return arr[i];
        }
    }
    return -1;
}

Solution with O(n) time and O(n) space.

private static int findDuplicate(int[] arr) {
    boolean[] visited = new boolean[arr.length - 1];
    for (int k : arr) {
        if (visited[k]) {
            return k;
        }
        visited[k] = true;
    }
    return -1;
}

Floyd’s Tortoise and Hare Algorithm

Assume array elements are from 1 to n-1 (instead of 0 to n-2) i.e. elements are 1 <= max(arr) <= n-1. Examples:-

Array = {1, 3, 2, 4, 3, 3}; O/P = 3
Array = {1, 1}; O/P = 1
Array = {3, 4, 5, 1, 2, 4, 4}; O/P = 4

Now it can be done in O(n) time and O(1) space without changing the original array. The idea is to traverse the array from left to right and use array elements as indexes from the chain. In this chain, we will always see a circle where the duplicate element with be the first element of the cycle. So, find the first node of this cycle. To find the first node of this cycle we will use the popular algorithm (from LinkedList) Floyd’s Tortoise and Hare algorithm.

Floyd’s Tortoise and Hare algorithm is a specific instance of the two-pointer approach designed for cycle detection. In this algorithm:-

  • The “tortoise” (slow) moves one step at a time.
  • The “hare” (fast) moves two steps at a time.

When they meet, a cycle is detected, and further steps help identify the cycle’s entry point, such as finding duplicates in an array.

public class Test {
    public static void main(String[] args) {
        int[] arr = { 1, 3, 2, 4, 3, 3 };
        System.out.println(findDuplicate(arr)); // 2
    }

    private static int findDuplicate(int[] arr) {
        int slow = arr[0], fast = arr[0];

        // Phase 1: Finding the intersection point
        do {
            slow = arr[slow];
            fast = arr[arr[fast]];
        } while (slow != fast);

        // Phase 2: Finding the entrance to the cycle
        slow = arr[0];
        while (slow != fast) {
            slow = arr[slow];
            fast = arr[fast];
        }
        return slow;
    }
}

In Phase-1:-

  1. Fast will enter the cycle first (or at the same time) (because it moving at double speed).
  2. In every iteration, the distance increases by one.

Phase 1: Finding the intersection point

  • In this phase, we use the Floyd’s Tortoise and Hare algorithm to detect a cycle:
  • slow moves one step at a time: slow = arr[slow]
  • fast moves two steps at a time: fast = arr[arr[fast]]
  • The loop continues until slow and fast meet, which indicates that there is a cycle in the array. The intersection point means there is a repeating element.

Phase 2: Finding the entrance to the cycle

  • Once the intersection point is found:
  • slow is reset to the start of the array: slow = arr[0]
  • Both slow and fast now move one step at a time: slow = arr[slow] and fast = arr[fast]
  • They will eventually meet at the entrance to the cycle, which is the repeating element. This element is returned as a duplicate.

Now let us see the solution for our original problem where array elements are from 0 <= max(arr) <= n-2.

Array = {0, 2, 1, 3, 2, 2} Output: 2
Array = {1, 2, 3, 0, 3, 4, 5} Output: 3
Array = {0, 0} Output: 0

To handle such an array, whenever we update slow and fast we will add 1. So that we can treat elements from 1 to n-1.

public class Test {
    public static void main(String[] args) {
        int[] arr = { 0, 2, 1, 3, 2, 2 };
        System.out.println(findDuplicate(arr)); // 2
    }

    private static int findDuplicate(int[] arr) {
        int slow = arr[0] + 1, fast = arr[0] + 1;
        do {
            slow = arr[slow] + 1;
            fast = arr[arr[fast] + 1] + 1;
        } while (slow != fast);
        slow = arr[0] + 1;
        while (slow != fast) {
            slow = arr[slow] + 1;
            fast = arr[fast] + 1;
        }
        return slow - 1;
    }
}

When we have an array where the smallest element is 0 why do we increase slow and fast by 1? Why not simply form a chain by following the array values? If we had simply followed the array element then at the 0th index we find out arr[0] = 0 (result), and then again this resultant element to go to that index i.e. arr[0] and it will make a self loop. It will end up with unnecessary cycles.

15. Allocate the Minimum Number of Pages

In the Allocate Minimum Number of Pages problem, you have a set of books, each with a certain number of pages. The goal is to allocate these books to a given number of students such that the maximum number of pages assigned to a student is minimized. Essentially, you’re trying to distribute the reading load as evenly as possible among the students. It is one of the popular interview questions.

Problem Statement:-

  • You’re given an array of integers, where each element represents the number of pages in a book.
  • You also have an integer m representing the number of students.
  • Your task is to allocate the books among the students such that the maximum number of pages assigned to a student is minimized.
  • The books must be allocated in a contiguous manner. Each student gets a consecutive sequence of books.
  • Every student must receive at least one book, and each book is assigned to exactly one student.

Example: If you have books with pages [12, 34, 67, 90] and 2 students, the optimal way to allocate the books is [12, 34] to one student and [67, 90] to the other, minimizing the maximum number of pages a student reads. This problem is typically solved using a binary search approach combined with a greedy algorithm. More Examples:-

  • Array = {10, 20, 30, 40}, k=2; O/P: 60 (As {10, 20, 30}, {40}}. Hence 60 is the maximum pages one student has to read.
  • Array = {10, 20, 30} k=1; O/P: 60 (As {10, 20, 30}). There is only one student.
  • Array = {10, 5, 30, 1, 2, 5, 10, 10}, k=3; O/P: 30 (As {10, 5}, {30}, {1, 2, 5, 10, 10}}). Hence 30 is the maximum pages students have to read.

Naive Recursive Solution

We need to choose k-1 cuts out of n-1 cuts. Total ways:- n-1Ck-1.
Example:- {10, 20, 30, 40}, k=2. Hence total ways:- 3C1 = 3. Hence we need to choose 1 cut out of 3 cuts.

nCr = n! / (r! * (n – r)!)

Example: 3C1
3C1 = 3! / (1! * (3 – 1)!)
3C1 = 3! / (1! * 2!)
3! = 3 × 2 × 1 = 6
2! = 2 × 1 = 2
1! = 1
3C1 = 6 / (1 × 2) = 6 / 2 = 3
public class Test {
    public static void main(String[] args) {
        int[] arr = { 10, 20, 30, 40 };
        int k = 2;
        System.out.println(minPages(arr, arr.length, k)); // 2
    }

    private static int minPages(int[] arr, int n, int k) {
        if (k == 1) {
            return sum(arr, 0, n - 1);
        }
        if (n == 1) {
            return arr[0];
        }
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            result = Math.min(result, 
              Math.max(minPages(arr, i, k - 1), sum(arr, i, n - 1)));
        }
        return result;
    }

    private static int sum(int[] arr, int start, int end) {
        int sum = 0;
        for (int i = start; i <= end; i++) {
            sum += arr[i];
        }
        return sum;
    }
}

Time Complexity:-

  • In the worst case, the function makes O(n^k) calls, where n is the number of books and k is the number of students.
  • Each call to minPages makes a sum call which takes O(n) time.
  • Thus, the overall time complexity is O(n^k * n) = O(n^(k+1)).

Space Complexity: In the worst case, the depth of the recursion is k, leading to a space complexity of O(k).

Binary Search-Based Solution for the Problem

This is a special problem where the array is not sorted but we will be using a binary search algorithm.

For array {10, 20, 10, 30} and k=2, the sum of all pages = 10 + 20 + 10 +30 = 70. The minimum value of all maximum pages = 30. Hence the answer will be in range [30, 70].

Res = (30 + 70) / 2 = 100 / 2 = 50. So, first, we will check whether 50 is the possible solution or not, and based on that we will choose left or right in [30, 50, 70]. New Range low=30, high = 50-1 = 49

Res = (30 + 49)/2 = 39
Res = (40 + 49)/2 = 44
Res = (40 + 43)/2 = 41
Res = (40 + 40)/2 = 40

Steps for binary search:-

  • Find the maximum element in the array (max) and the sum of all elements (prefixSum) in the array. The answer will be in the range of [max, prefixSum]. Apply binary search on this range.
  • Find the mid and check whether it is a feasible solution or not.
    • If yes, then update the result with mid. Now, go to the left part high = mid - 1 because numbers < mid can be also the solution and our task is to find the minimum value.
    • Else go to the right side lower = mid + 1

In the isFeasible() method count the number of portions that can be made by grouping contiguous array elements such that each portion sum = mid. Return count <= k.


public class Test {
    public static void main(String[] args) {
        int[] arr = { 10, 20, 30, 40 };
        int k = 2;
        System.out.println(minPages(arr, k)); // 2
    }

    private static int minPages(int[] arr, int k) {
        // find max & sum of array elements
        int max = 0, sum = 0;
        for (int i : arr) {
            sum += i;
            max = Math.max(max, i);
        }

        // binary search
        int low = max, high = sum, res = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (isFeasible(arr, mid, k)) {
                res = mid;
                // check number < mid (left half)
                high = mid - 1;
            } else {
                // check number > mid (right half)
                low = mid + 1;
            }
        }

        return res;
    }

    private static boolean isFeasible(int[] arr, int mid, int k) {
        int req = 0, sum = 0;
        for (int a : arr) {
            if (sum + a > mid) {
                req++;
                sum = a;
            } else {
                sum += a;
            }
        }
        return req <= k;
    }
}

For array {10, 5, 20}, and k=2
Mid = (20 + 35)/2 = 27, res = 27
Mid = (20 + 26)/2 = 23, res = 23
Mid = (20 + 22)/2 = 21, res = 21
Mid = (20 + 20)/2 = 20, res = 20
Now low == high. And in the next iteration low = 20, high = 18, and due to while(low <= high) loop breaks.

Time complexity O(n * log(sum-max)). Upper bound = O(n * log sum). This solution could be better if the sum is not very very high, else dynamic programming will work better having O(n^2 * k) time.

16. Number and the Digit Sum

Given a positive value N, we need to find the count of numbers smaller than or equal to N such that the difference between the number and the sum of its digits is greater than or equal to the given specific value K.

Input:N = 13, K = 2
Output: 4
Explanation:
10, 11, 12, and 13 satisfy the given condition shown below, 
10 – sumofdigit(10) = 9 >= 2
11 – sumofdigit(11) = 9 >= 2
12 – sumofdigit(12) = 9 >= 2
13 – sumofdigit(13) = 9 >= 2 

To achieve a logarithmic time complexity (O(log N)) and constant auxiliary space (O(1)) for this problem, we can leverage binary search. The idea is to count numbers that satisfy the condition using binary search. Here is the approach:

  1. Define a function to check if a number X satisfies the condition X−sum of digits(X)≥ K.
  2. Use binary search to count the numbers between 1 and N that satisfy the condition.

Let’s say N = 50 and K = 5.

  1. Range: We start with the entire range from 11 to 5050.
  2. Initial Range Check:
    • low = 1, high = 50
    • Calculate mid: (low + high)/2 = 25
  3. Check Mid:
    • Calculate the sum of digits of 25: 2+5=7
    • Condition check: 25 – 7=18, which is greater than 5.
    • Since 25 satisfies the condition, count all numbers from 25 to 50 (26 numbers), and adjust high to 24.
    • count = 26
    • low = 1, high = 24
  4. Next Range Check:- mid = (low + high)/2 = 12
  5. Check Mid:
    • Calculate the sum of digits of 12: 1+2=3
    • Condition check 12−3=9, which is greater than 5.
    • Since 12 satisfies the condition, count all numbers from 12 to 24 (13 numbers), and adjust high to 11.
    • count = 26 + 13 = 39
    • low = 1, high = 11
  6. This process continues.
public class CountNumbers {
    private static int sumOfDigits(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }

    private static boolean satisfiesCondition(int num, int K) {
        return (num - sumOfDigits(num)) >= K;
    }

    public static int countNumbers(int N, int K) {
        int low = 1, high = N, count = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (satisfiesCondition(mid, K)) {
                count += high - mid + 1;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int N = 100;
        int K = 10;
        System.out.println("Count of numbers: " + countNumbers(N, K));
    }
}

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Leave a Comment

Your email address will not be published. Required fields are marked *