Searching and Sorting: Minimum number of swaps required to sort an array
Problem Statement: You are given an array of distinct elements. You need to find the minimum number of swaps required to sort the array. Example Input : {4, 3, 2, 1} Output : 2 We need to swap index 0 with 3 and 1 with 2 to make the array sorted. Solution The solution is […]
Searching and Sorting: Sort Integers by The Number of 1 Bits
Problem Statement: You are given a array. You have to sort the integers in ascending order by the number of 1’s in their binary format. Example Input: arr[] = {1, 2, 3, 4, 5, 6}; Output: 3 5 6 1 2 4 Explanation: 3 – 0011 5 – 0101 6 – 0110 1 – 0001 […]
Searching and Sorting: Product of array except itself.
Problem Statement: You are given an array, you need to return an array of the product such that the prod[i] is equal to the product of all the element of arr[] except arr[i]. Example Input = {1, 2, 3, 4, 5} O/p = {120, 60, 40, 30, 24} 2 * 3 * 4 * 5 […]
Searching and Sorting: print all subarrays with 0 sum
Problem Statement: You are given an array and you need to print all the sub array with the sum 0. Example Input: [ -3, -1, 0, 4 ] Subarrays with zero-sum are { -3, -1, 0, 4 } { 0 } Solution The solution is very simple. We will take the help of hashing. We […]
Searching and Sorting: Merge 2 sorted arrays
Problem Statement: You are given two sorted arrays x[] and y[] of size m and n, You need to merge elements of array x[] to y[] by maintaining sorted order. Example Input: arr1[] = {20}; arr2[] = {5, 6}; Output: arr1[] = {5} arr2[] = {6, 20} Solution The solution is very simple, we begin […]
Maximum sum such that no two elements are adjacent
Problem Statement: You are given an array, you need to find the maximum sum of subsequence where no 2 numbers in the sequence are adjacent. So {3, 4, 5, 6} The max is 10 {6, 4}. Solution The solution is very simple. We take 2 variables: incl = what will have Max sum including the […]
Searching and Sorting: Maximum sum such that no two elements are adjacent
Problem Statement: You are given an array, you need to find the maximum sum of subsequence where no 2 numbers in the sequence are adjacent. So {3, 4, 5, 6} The max is 10 {6, 4}. Solution The solution is very simple. We take 2 variables: incl = what will have Max sum including the […]
Searching and Sorting: Count all distinct pairs with difference equal to k
Problem Statement: You are given an unsorted array, and an integer K. You need to get all distinct pairs with difference equal to k. Example Input: arr[] = {1, 5, 4, 2}, k = 3 Output: 2 There are 2 pairs with difference 3, the pairs are {1, 4} and {5, 2} Solution We can […]
Searching and Sorting: Search an array where adjacent differ by at most k
Problem Statement: You are given an array and has a difference of atmost k. Given a key ‘x’, we need to find the index value of ‘x’. Example Input : {1, 2, 3, 4, 3} k = 1 x = 3 Output : 2 First index of 3 is 2. Solution The solution is […]
Searching and Sorting: Maximum and minimum of an array using minimum number of comparisons
Problem Statement: You are given an unsorted array, you need to get the maximum and minimum element of the array using minimum comparisons. Solution There are multiple ways to solve this problem: 1. Linear search: Here we simply search the whole array and update minimum and maximum values accordingly. But here the number of comparisons: […]