We’re given a function in the format of f(x). We have to find the minimum absolute difference between f(x) and given number k over a range (0 – 10^6). This article assumes you know the working principle of binary search. If you don’t know, please go and check out the binary search. To understand this concept, let’s assume… Read More »
In a prison, there are N cells. The positions of the cells are given in an array. The Jailer has to place all the prisoners in the cells in an ordered manner such that minimum distance between any two prisoners is as large as possible. You have to find that distance. Note: The cells are in a straight… Read More »
Given 2 sorted arrays A and B of size N each. Print the sum of the middle elements of the array obtained after merging the given arrays. Examples: Input: arr1: 1 2 4 6 10 Input: arr2: 4 5 6 9 12 Output: 11 (5 + 6) The approach is similar to that of Merge function of Merge… Read More »
There is an array arr[] of length N. Your task is to find the sum of the minimum elements of each possible sub-array of the array. Examples: Input : arr[] = {2, 4, 6, 8, 10} Output : 75 Explanation : Min of all sub-arrays: {2} – 2 {2, 4} – 2 {2, 4, 6} – 2 {2,… Read More »
Given an array arr[] of n positive integers and q queries, in which each query have an integer k. For each query, the task is to output the minimum size of subarray whose binary representation of each elements if concatenated will have at least k number of set bits. If no such array exist, print -1. Examples: Input… Read More »
Given a sorted rotated array, the task is to find index of minimum element of the array. Following solution assumes that all elements are distinct. Examples: Input : arr[] = {5, 6, 1, 2, 3, 4} Output : 2 Minimum element in the array is 1, hence index will be 2 Input : arr[] = {2, 3, 4,… Read More »
Given an array of integers, write a function that returns true if there is a triplet (a, b, c) that satisfies a2+b2=c2 Example: Input: arr[] = {8, 1, 4, 6, 10} Output: True There is a Pythagorean triplet (8, 6, 10). Input: arr[] = {1, 2, 4, 3} Output: False There is no Pythagorean triplet. Approach: The problem… Read More »
Given a string find the character which occurs a minimum number of times. Note: If multiple such characters exist output anyone. Example: Input: S = abbccdd Output: a As frequency of every element is more than that of a Input: S = abccdd Output: b or Output: a Both the outputs are acceptable according to given conditions. Naive… Read More »
Write an efficient C program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum. Examples: Input : {-2, -3, 4, -1, -2, 1, 5, -3} Output : 7 The subarray {4,-1,-2,1,5} gives the maximum sum among all other possible sub-arrays. Algorithmic Paradigm: Divide And Conquer To apply Divide and… Read More »
Given a string A, compute the minimum number of characters you need to delete to make resulting string a palindrome. Examples: Input : baca Output : 1 Input : cplusplus Output : 6 Below approach will use modified Levensthein distance. We would like to pass to modified Levensthein both original string and its reverse. C++ Implementation: Output: To… Read More »
