Arrays

Question:- We are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing. Give an algorithm to find the missing integer. Input:- 1, 2, 4, 6, 3, 7, 8 Output:- 5 Brute Force Solution:- One simple solution to this is, for each number in 1 to n check whether that number is in the given array or not. Return the number that is not present. Here is the code module for …

Question: Given an array of n numbers. Give an algorithm for finding the element which appears maximum number of times in the array? Input: 3, 2, 1, 2, 2, 3 Output: 2 The previous method required us to sort the array. But what if we do not want to sort the array. We can also solve this problem using 2 scans of the array. We cannot use the negation method used to check duplicates because of the number of repetitions. In the first scan, instead of negating -> add the …

Question: Given an array of n numbers. Give an algorithm for finding the element which appears maximum number of times in the array? Input: 3, 2, 1, 2, 2, 3 Output: 2 This problem can be done by brute force method. Now let us try to optimize this problem further. We need to reduce the time complexity. We used 2 for loops in the brute force approach. This is not necessary. Another approach can be:- Sort the entire array. Start scanning the array from the beginning and keep counting the …

Question: Given an array of n numbers. Give an algorithm for finding the element which appears maximum number of times in the array? Input: 3, 2, 1, 2, 2, 3 Output: 2 One simple and a brute force solution to this is, for each input element check whether there is any element with same value and for each occurrence, increment the counter. Each time, check the current counter with the max counter and update it if this value is greater than max counter. This we can solve just by using …

Question: Given an array of n numbers, give an algorithm for checking whether there are any duplicated elements in the array or not? Input: 4, 8, 15, 16, 23, 42 Output: NO Input: 4, 8, 4, 15, 23, 42 Output: YES Another possible and better way to solve this problem based on a certain condition. Let us assume that the array elements are positive numbers and also all the elements are in the range 0 to n-1. For each element A[i], go to the array element whose index is A[i]. …

Question: Given an array of n numbers, give an algorithm for checking whether there are any duplicated elements in the array or not? Input: 4, 8, 15, 16, 23, 42 Output: NO Input: 4, 8, 4, 15, 23, 42 Output: YES Now the question arises, if we can improve the complexity of the above problem. We discussed the most basic method to find duplicates here. The time complexity can be improved by sorting the given array. After sorting, all the elements with equal values come adjacent to each other. Now, …

Question: Given an array of n numbers, give an algorithm for checking whether there are any duplicated elements in the array or not? Input: 4, 8, 15, 16, 23, 42 Output: NO Input: 4, 8, 4, 15, 23, 42 Output: YES This is one of the simplest problems. One obvious solution to this is, exhaustively searching for duplicated elements in the array. That means, for each input element check whether there is any element with the same value. This we can solve by using two simple for loops. The code …

Binary Search only works when your input list of elements is already sorted. This is main and the most important condition for this search algorithm. Unlike Linear Search, we take advantage of the sorted nature of the array. We always search in the middle portion of the array. Working of Binary Search: Let us say we have this sample array. Note that this array is sorted. I want to search for the element 12 in this array. One way, I can proceed is by dividing the array in 2 halves. …

Iterative way: 1) Initialize start and end indexes. start = 0, end = n-1 2) In a loop, swap arr[start] with arr[end] and change start and end as follows. start = start +1; end = end – 1 Time Complexity: O(n) Recursive Way: 1) Initialize start and end indexes start = 0, end = n-1 2) Swap arr[start] with arr[end] 3) Recursively call reverse for rest of the array. Time Complexity: O(n)

Counting sort is not a comparison sort algorithm. The sorting techniques that work on comparison are: Selection Sort Bubble Sort Insertion Sort Merge Sort Quick Sort The best time complexity you can achieve in any of these sorting techniques is . However, is some very specific cases, you can achieve an even faster computation time of . This is made possible by an assumption. We assume that the input data set is within a finite limit. For example, if you want to sort some characters of the English alphabet. You …