Arrays

Question: Given an array of n elements. Find two elements such that their sum is equal to a given element ‘K’ ? Input: arr [] = {42, 23, 15, 16, 8, 4} and element K = 58 Output: 16, 42 We discussed the approach to this problem using 2 loops in this post. But obviously this was not a good approach as it had a time complexity of O(n2). The time taken to solve such a problem if the array has elements in range of million will be very high. …

Question: Given an array of n elements. Find two elements such that their sum is equal to a given element ‘K’ ? Input: arr [] = {42, 23, 15, 16, 8, 4} and element K = 58 Output: 16, 42 To understand the problem statement a little more, we are given with an array of ‘n’ elements and another element ‘K’. We need to find if there exists 2 elements in the given array such that their sum equals the given element K. The array is not sorted. One simple …

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 We discussed a method to perform this task using an extra array to count the occurrences of elements, but this approach took an extra space of the range of elements of array. If we have a very wide range, then we …

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 …