Arrays: Given an array find the duplicate number
Problem Statement: You are given an array of integers having “n+1” integers. The integers in the array will be from [1, n]. There will be one duplicate number and return the duplicate number. Example: Input: arr = {1, 2, 1} Output: 1 Solution: We can solve this problem in number of different methods. Some of […]
Arrays: Minimize the maximum difference between the heights
Problem Statement: You are given an array that represents the height of the towers. You are also given a value “k”. You need to either increase or decrease the height of every tower by “k”. Your task is to minimize the difference between the heights of the longest and the shortest tower. Example: Input array: […]
Arrays: Given an array, rotate it one time
Question: Given an arrays, rotate it one time cyclically Example: Input : arr = {1, 2, 3, 4, 5, 6, 7, 8} Output: rotating it one time will become {8, 1, 2, 3, 4, 5, 6, 7} We can modify the question, to rotate the array “k” times. We can solve this question by multiple […]
Arrays: Find the union and intersection of two sorted arrays
Question: Given 2 sorted arrays, find the union and intersection Example: Input : arr1 = {1, 3, 4, 6, 8} arr2 = {2, 3, 5, 7, 8} Output: Union : {1, 2, 3, 4, 5, 6, 7, 8} Intersection : {3, 8} Union of 2 arrays is to print all the unique elements from both […]
Arrays: Move all the negative number in beginning
Question: Given an unsorted array with positive and negative elements, move all the elements to the beginning of the array. Example: Input : {5, -6, 7, -8, 9, -10} Output : {-8, -6, -10, 5, 9, 7} We can solve this by many different methods. Some of the methods are discussed below: 1. By Sorting […]
Arrays: Find the k’th smallest/largest element in an array
Question: Given an unsorted array with distinct elements, you are also given an integer “k”. You need to find the k’th smallest/largest element in the array. Example: Input : {5, 6, 7, 8, 9, 10} k = 2 k’th smallest element = 6 k’th largest element = 9 Solution: We can solve this question by […]
Find the Maximum and minimum of an array
Question: Given an array, find the Max and Min of the array, with less number of comparisons. Example: Input : {5, 4, 3, 2, 1} Max element = 5 Min element = 1 Solution: We can solve this problem by different ways, some of them are explained in this article are: 1. Iterative Method 2. […]
Reverse an array
Question: Given an array, print that array in reverse order. Example: Input : {5, 4, 3, 2, 1} Output : {1, 2, 3, 4, 5} Solution: We can solve this problem by different ways, some of them are explained in this article are: 1. By using C++ STL 2. By taking a temp variable 3. […]
Min Edit Distance
In this tutorial we shall solve min edit distance with help of DP. Problem statement: You are given 2 strings. You need to find min distance such that the strings are equal. You will be able to: 1. Insert a character 2. Delete a character 3. Replace a character. Example 1: String 1 = ram […]
Egg Dropping Problem
In this tutorial we shall solve another classical DP problem. This problem is bit complex to understand. Hence first we shall solve this problem with help of recursion. Later we shall see how to solve it using DP. Problem Statement: You are given “n” floors and “m” eggs. You need to find from which floor […]