Count the number of 1’s in an array sorted in decreasing order.
Question: You are given an array that is sorted in decreasing order and has only 0’s and 1’s. You need to find the number of 1’s present in it. Example: array = {1,1,1,1,1,0,0,0} Output = 5 array = {1,1,1,1} Output = 4 array = {0,0,0,0,0} Output = 0 Solution: We can solve it by binary […]
Get the rotation count in sorted rotated array
Problem Statement: You are given an array, you need to check if the array is sorted and rotated. Example: array = {6, 7, 1, 2, 3, 4, 5} Output; True array = {1, 2, 3, 4, 5} Output; False Because it is not rotated Solution: We can solve it by modified binary search. What we […]
Search An Element in Bitonic Array
Problem statement: Given an bitonic array, find the max element in that. Example: Array {1, 2, 3, 4, 5, 4, 3, 2, 1}; key = 1 Output = 0 or 9 A bitonic array is an ascending sorted array where, after a particular element, the array starts descending. In our example above, the array is […]
Find maximum element in Bitonic Array
Problem statement: Given an bitonic array, find the max element in that. Example: Array {1, 2, 3, 4, 5, 4, 3, 2, 1}; Output = 5 A bitonic array is an ascending sorted array where, after a particular element, the array starts descending. In our example above, the array is ascending till element 5 and […]
Peak Element
Problem Statement: You are given an unsorted array and you need to send the index of peak element. Understanding what is Peak element? 1. An element who is greater than both of its neighbor. Example array = {1, 2, 5, 4, 3}. Here peak element is 5 and index is 2. 2. An element, if […]
Find the index of first 1 in an infinite sorted array of 0s and 1s
Problem statement: You are given a sorted array of infinite length of 0’s and 1’s. You need to find the first occurrence of 1. Example: array = {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1} Output: 1 is found at the index 10. Solution: We can […]
Find position of an element in an Infinite Sorted Array
Question: You are given an array in sorted order, but it is infinite. You are also given an key element. You need to check if the element is present in that infinite array. array = {1, 2, 3, 4, 5, 7, 8, 9, 10, 100, 200, 300} key = 8 Element is found at index […]
Find Ceil of an element in a Sorted Array
Question: You are given an array and a key. You need to return the Ceil of that element. What is Ceil? If you are given a number say “5.8”, the floor of that number is 5 and ceil is 6. What will be the Ceil in this question? array = {1, 2, 3, 4, 6, […]
Find Floor of an element in a Sorted Array
Question: You are given an array and a key. You need to return the floor of that element. What is floor? If you are given a number say “5.8”, the floor of that number is 5 and ceil is 6. What will be the floor in this question? array = {1, 2, 3, 4, 6, […]
Searching in a Nearly Sorted Array
Problem Statement: Given a sorted array where an element that should be present in i’th position, can be present in i-1’th position or i+1’th position. You are also given a key element. Check if the key element is present or not. Example: array = {1, 2, 3, 5, 4, 6, 7}; => Here element 4 […]