Algo#50: Find k element pairs out of given array which adds to SUM

Find k element pairs out of given array which adds to SUM

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#49: Sort the input character array based on the given dictionary order.

Sort the input character array based on the given dictionary order.

E.G. If input word is “SHEEP“, sorting will make it as “EEHPS“.

But in the given dictionary, E may not be at first. As per the dictionary in given problem, if P is first, S followed and E later and finally H.

Then sorted array should be “PSEEH“.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#32: Generate spiral matrix or helical matrix.

It seems very easy problem of just printing 2D matrix in some format. But it includes many corner cases which needs to be taken care of. Such problems can test your coding practice.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#26: Binary Search In Unbounded Array

Binary Search in Unbounded array.

Following is simple algorithm for above problem.

Step 1: Locate lower and upper bound using jump at every 2^k location
Step 2: Do binary search within located bounds.

Following is implementation of above algorithm in c++ language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#25: Find kth smallest from given 2 sorted array.

Finding kth smallest element from given 2 sorted array is not big deal if we are allowed to do it in O(K) or O(N+M). But what if you are asked to do it less than that. Can we use binary search technique to reduce complexity as given array are sorted !!

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#24: Find min and max from given array.

Given problem of finding min and max from given array seems to be very trivial problem. But what if you are asked to do it in less than 2N-3 comparisons!

Following is simple algorithm for above problem.

Step 1: Partition given array in 2 parts.
        1.1: Compare 2 element pairs for all elements.
        1.2: Put min out of this 2 elements in list-1 and max out of this 2 elements in list-2.
Step 2: Find min & max from partial lists.
        2.1: Find running min from list-1.
        2.2: Find running max from list-2.

Though at first look, given algorithm seems to have other 2N space for storing partial list with 3N/2 -1 comparisons to find min & max. But making twist during implementation can make above algorithm to run in O(1) space complexity and 3N/2+3 comparisons only.
.

Following is implementation of above algorithm in c language with twist to reduce space complexity.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#17: Check whether array is sorted or not using recursion

This program basically test your recursion skills. So what should be our approach when questions like this comes.

When we are solving any problem with recursion, we have to identify datum which we are going to process in one iteration of recursion. Here in our case, we will process one element of array at a time, it means remaining n-1 element should be process by recursion.

Following is simple recursive algorithm for Checking array for sorted property using recursion.
Step 1: If we are having only one element, then by default it is sorted. Success.
Step 2: Otherwise, relationship between first and second element. first element <= second element. If not then failure, else go to step 3.
Step 3: Get success or failure indicator for remaining array of n-1 element using recursion.If remaining array comes out to be sorted, then whole array is sorted.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#13: Cyclic right shift of bits in number

Manipulation of bits are very crucial if you can apply it properly in your computing because it is one of the fastest technique for computing.

Following is simple algorithm for finding Cyclic Right Shift of bits in given number by S bits.

Step 1: Take right S bits of number, and shift it right by R-S positions, where R is number of total bits in given number, call it Partial-1.
Step 2: Take left R-S bits of number, and shift it left by S positions, call it Partial-2.
Step 3: Do OR operation between Partial-1 and Partial-2.

Following is implementation of above algorithm in c language in one line.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#12: Binary Search Technique with Duplicates - Find Last Occurrence Index

Binary search technique is very well known for its fast search result provided given array is sorted.

Following is simple iterative algorithm for Binary Search (Last Occurrence) in Sorted Array With Duplicates.
Step 1: Set l(left) at start index of array.
Step 2: Set r(right) at end index of array.
Step 3: Set left-border at start index of array.
Step 4: Set right-border at end index of array.
Step 5: Repeat following until r>=l
        5.1: Initialize mid using current left and right index (l+(r-l)/2).
      5.2: If element at mid index is target element and element at after mid index is different than target element, then return mid index as successful binary search.
        5.3: Otherwise if element at mid index is greater or equal to target element, then replace r = mid -1
        5.4: Otherwise if element at mid index is less than target element, then replace l = mid +1
Step 6: If you reach here, element you are searching for is not found.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#11: Binary Search Technique with Duplicates - Find First Occurrence Index

Binary search technique is very well known for its fast search result provided given array is sorted.

Following is simple iterative algorithm for Binary Search (First Occurrence) in Sorted Array With Duplicates.
Step 1: Set l(left) at start index of array.Step 2: Set r(right) at end index of array.
Step 3: Set left-border at start index of array.
Step 4: Set right-border at end index of array.
Step 5: Repeat following until r>=l
        5.1: Initialize mid using current left and right index (l+(r-l)/2).
      5.2: If element at mid index is target element and element at before mid index is different than target element, then return mid index as successful binary search.
        5.3: Otherwise if element at mid index is greater or equal to target element, then replace r = mid -1
        5.4: Otherwise if element at mid index is less than target element, then replace l = mid +1
Step 6: If you reach here, element you are searching for is not found.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#10: Binary Search Technique

Binary search technique is very well known for its fast search result provided given array is sorted.

Following is simple iterative algorithm for Binary Search in Sorted Array.

Step 1: Set l(left) at start index of array.

Step 2: Set r(right) at end index of array.
Step 3: Repeat following until r>=l
        3.1: Initialize mid using current left and right index (l+(r-l)/2).
        3.2: If element at mid index is target element, then return mid index as successful binary search.
        3.3: Otherwise if element at mid index is greater than target element, then replace r = mid -1
        3.4: Otherwise if element at mid index is less than target element, then replace l = mid +1
Step 4: If you reach here, element you are searching for is not found.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.