Majority Element of an Array (Moore's Algorithm)
An integer x in array arr of n elements is the majority element if and only if x appears more than n/2 times in A. – If n is odd then it should appear at least (n+1)/2 times – If n is even then it should appear at least (n/2) + 1 times Array: 1 […]
Print array in the forward and backward direction recursively
Write a recursive function which will print an array in forward and backward order (depending on a parameter). The signature of the function should be /* If the array is 1 2 3 4 5, then Output should be * 1 2 3 4 5 – if (forward == true) * 5 4 3 2 […]
Find kth element in union of two arrays
Given two sorted arrays of size m and n respectively. Find the kth element in the merged result of A and B. For example, If the inputs (A, B & K ) are as given below Then the merged result of the two arrays will be And the 6th (K’th) element = 8
Missing and repeating number in an array
Given an unsorted array of size n with numbers ranging from 1 to n. One number from set {1, 2, 3, …, n} is missing and one number occurs twice in array. For example: If the size is 6, then array may be int arr[] = {1, 5, 3, 4, 1, 2}; Where 1 is […]
Continuous sub-array with given sum
Given an array of positive integers and a number ‘k’. Find continuous subarray whith sum of all the elements = k. For example.. Array k Output ——————— —— ————– {2, 4, 17, 9, 6, 3} 18 FOUND. arr[3] thru arr[5] {1, 0, 4, 0, 2} 7 FOUND. arr[0] thru arr[4] {1, 0, 4, 0, 2} […]
Merge two arrays into one
There are 2 sorted arrays of size m and m+n respectively. First array (of size m) has m elements and Second array (of size m+n) has only n elements (last m positions are blank). So, the total number of elements in both the arrays is m+n (m in first and n in second). Write code […]
Number of inversions in an Array.
Write a function which will accept an array and count the number of inversions in the array. Inversions in an Array are a measure of how far an array is sorted. Two elements in an array (say arr[i] and arr[j]) are said to be forming inversion iff, arr[i] > arr[j] AND i < j
Freeing memory allocated to n-dim array using free
Yesterday we learned about how to allocate memory on heap for an n-dim array using Malloc. Today let us see how to deallocate the memory on heap using free. It is Simple if we are deallocating normal pointers or pointers pointing to a one-dimensional array. How will deallocate memory of an n-dim array on heap?
Allocating memory to n-dim Array on heap
Dynamic arrays are on heap. If an array is stored on heap, its address must be stored in pointer variables, else there will be no way to access the array. Let us assume the Array to hold integers. Write a code to allocate memory to a 2-dim array and then generalize it to allocate memory […]
Search in a matrix sorted on rows & columns
Given a matrix whose each row and column is sorted as shown below 10 20 30 40 15 25 35 45 27 29 37 48 32 33 39 50 Write an algorithm that will search for the matrix for a value (say 37) and print the index of position where it finds the value. If […]
