Algo#43: Write basic function to implement atoi - Alpha to Integer

Function atoi is used to convert alphabetical string to integer. We can parse given string one character at a time, and convert it to integer. To make conversion fast enough, we can use bits manipulation for faster calculation.

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#40: Union Find Data Structure in C

Union Find Data Structure is useful to reduce time complexity in many problems e.g. Kruskal’s algorithm. 

Following is implementation of above data structure in c language.

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

Algo#37: Calculate x^y in less time complexity than O(y)

Brute force way to calculate power of any number is to multiply given x number, power y times. But recursion can drastically reduce time complexity.

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#27: Count number of 1's in given number

Brute force method to count number of 1's in given number is to iterate through each bit and check if it is 1, then increment counter. But it will take 32 checks (assuming 32 bit number).

Can we do better? Is there any way by which we don't need to check all bits? What if we iterate as many times as numbers of 1's. To achieve it, we have to remove 1 from number at each iteration, then only at last when no one is remaining in number, we can stop.

Manipulation of bits in number is only solution to reduce iteration. By doing x-1, we can eliminate last 1 from given number but it will introduce tailing 1's in number. But those should be not an issue for us. Because we have AND weapon to get rid of all tail 1's.

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#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#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#21: Give next higher boundary number.

To give next higher boundary of number, is used when allocating memory to structure, so that access to its members are fast.

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#19: Convert given number in different endian system than your system.

There are mainly two types of system based on endianness available to us.
1) Big endian
2) Little endian

To convert one number other endianness system, we have to change order of all bytes.

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#16: Solve 8-Queen Problem.

8-Queen problem ask us to set 8 queen on board such that they don't attack each other by any direction. We must be knowing that queen can move row wise, column wise and in both diagonals also.

First thing we need here is, way to check whether we can put chosen queen at particular location or not. We can put queen only if satisfy following criteria.
1. It should be unique in its row.
2. It should be unique in its column.
3. It should be unique in its both diagonals.

Lets say we made some function called Check() which tell whether current queen have any conflicts with previous queens that we have set. Now we are ready to take up our back tracking algorithm.

Following is simple algorithm for finding 8-Queen Problem.

Step 1: If we have filled all rows of board than we are done.
Step 2: Otherwise try all possible columns for current queen and check if it has any conflicts with any previous queen, if not then set remaining queens.

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#14: Set specified bits range in number.

Set specified bits range in number.

Following is simple algorithm for setting bits range in given number.

Step 1: Make mask for start index to end index.
        1.1: First step to make mask is, set 1 in each position from 0 to end index, call it mask-1.
        1.2: Then same way, set 1 in each position from 0 to start index, call  it mask-2.
        1.3: XOR mask-1 and mask-2, which will give us our desired mask having 1 set from start to end index.
Step 2: Do OR operation between given number and mask.

Following is implementation of above algorithm in c language in 1 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#7: Closest Value Search in Binary Search Tree (BST)

Closest Value Search in Binary Search Tree (BST) means returning nearest value in BST to given key.

Following is simple algorithm for finding Closest Value in BST.

Step 1: Current root itself is NULL, then closest value is zero.
Step 2: If current root matches target key value, then closest value is key itself.
Step 3: Otherwise, consider current root as closest value and do following.
        3.1: If key is smaller then current root, find closest value on left side tree of current root recursively and call it RecursiveClosest.
        3.2: If key is larger then current root, find closest value on right side tree of current root recursively and call it RecursiveClosest.
Step 4: Return current root or RecusiveClosest depending on which ever is nearer to target key.

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.