Arrays

Question: Given an array with n+2 elements, all elements of the array are in range 1 to n and also all elements occur only once except 2 numbers which occur twice. Find those 2 repeating numbers. Input: arr[] = {6, 2, 6, 5, 2, 3, 1} Output: 6 2 One simple way is to scan the complete array for each element of the input elements. That means use two loops. In the outer loop, select elements one by one and count the number of occurrences of the selected element in…

Question: Given an array of positive integers, all numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time and constant space. Input:- arr[] = {1, 2, 3, 2, 3, 1, 3} Output:- 3 This is a very simple problem. The basic and naive approach will be to scan the complete array and keep a track of each element. We need to count the occurrence of each element and see if its even or odd. This would be a very…

Question: Write a program to rotate an array arr[], having a size ‘n’ by ‘d’ elements? Input: arr[] = { 4, 8, 15, 16, 23, 42, 99 }, d = 3 Output: 16, 23, 42, 99, 4, 8, 15 Let us suppose our array is in this way: On rotating the array by 3 elements, it should look like: We can do this by rotating the array one element at a time. We discussed it in this post. We can also use the REVERSAL Algorithm to rotate the array. This…

Question: Write a program to rotate an array arr[], having a size ‘n’ by ‘d’ elements? Input: arr[] = { 4, 8, 15, 16, 23, 42, 99 }, d = 3 Output: 16, 23, 42, 99, 4, 8, 15 Let us suppose our array is in this way: On rotating the array by 3 elements, it should look like: To solve the above problem, we can adopt this following technique- Create a function that rotates the entire array by one element at a time. To rotate by one, store arr[0]…

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 We solved this problem using array summation here. We can also utilize the property of XOR to solve this problem. The major property of XOR that we will be using is A XOR A = 0. Thus, the steps involved…

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 We solved the same problem via sorting here. Another solution to the problem is possible that has a even smaller time complexity and requires just a single scan of the array. The technique involved is:- Using the summation formula, get…

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 After the brute force method we can also use another method to find the missing number in an array. This technique involves sorting the array. Sort the array and give it a linear scan, if there is a difference between…

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…