Category Archives: Algorithm

Find Seed of a Number

A number X is said to be ‘seed’ of number Y if multiplying X by its digit equates to Y. For example, 123 is a seed of 738 coz 123*1*2*3 = 738. Now given a number find all its ‘seed’. Solution:

Count Pairs of Numbers with a Given Difference K

Given an unsorted array and a number n, find if there exists a pair of elements in the array whose difference is n. Return count of such pairs. Example k=4 and a[]={7,623,19,10,11,9,3,15} Output should be : 6 Pairs can be: 7,11 7,3 6,10 19,23 15,19 15,11 Solution: Time Complexity: O(NLogN) Space Complexity: O(1)

Number of Trailing Zeros in Factorial of a Number

Write a program to output the number of consecutive trailing zeros in the factorial of a number? Solution: 1. The number of trailing zeros in a number is equivalent to the power of 10 in the factor of that number. 2. The number power of 10 in the factors is the same as the minimum Read More →

Passing Car East or West Codility

A non-empty zero-indexed array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road. Array A contains only 0s and/or 1s: 0 represents a car traveling east, 1 represents a car traveling west. The goal is to count passing cars. We say that a pair of Read More →

Largest subarray with equal number of 0s and 1s

Problem: Given an binary array containing only 0s and 1s, find the largest subarray which contain equal no of 0s and 1s. Examples: Input: arr[] = {1, 0, 1, 1, 1, 0, 0,0,1} Output: 1 to 8 (Starting and Ending indexes of output sub array) Implementation: In this method,use two nested loops. The outer loop Read More →

Counting Sort

Counting sort is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set. Integers which lie in a fixed interval, say k1 to k2, are examples of such items. Algorithm: 1. Count for every key j, 1 ≤ j ≤ m how often it occurs in the Read More →

Sort Elements By Frequency

Problem: You are given an array. You have to sort the array elements in decreasing order of their frequency. eg. [2,3,4,2,8,1,1,2] Output: [2 2 2 1 1 3 4 8] Solution: Method 1 (Use Sorting) 1) Use quick sort algorithm to sort the elements O(nlogn) 2) Scan the sorted array and construct a 2D array Read More →

Group all Words in Set of Anagrams of Each Other in Dictionary

Problem: Given a dictionary with set of words in it. Write a program to group all words which are anagrams of each other in to sets. For example – Input: “bat”, “tar”, “xyz” , “tab”, “tar” Output:[["bat", tab"], ["tar", rat"],”xyz” ] Thi sproblem was asked in amazon interview. Steps: 1)Use some sort of a hash Read More →

Find Anagrams in array of Strings

Problem: You are given an array of strings and you have to print all the anagrams within the array. What is anagram – For those who don’t know, two words are anagrams if they contain the same characters. We have already discussed how to check if 2 strings are anagrams here. Solution: Let’s use this Read More →

Find the Minimum Element in the Rotated Sorted array

Problem : Find the minimum element in the rotated sorted array. For example we have array as – 1,3,6,9,12,15. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 12,15,1,3,6,9 Solution – The answer to this lies on the fact that if we can find the point on Read More →

Deleting all Leaves from a Binary Tree

Problem: Given a binary tree, how do you remove leaves of it? Solution: By using post-order traversal we can solve this problem (other traversals would also work). Time Complexity: O(n). Where is numbe of nodes in tree. Write or Comment if you find anything incorrect or better approach.

Find a Pair Whose Sum is Closest to Zero in Array

Problem: This problem is also called minimum absolute sum pair. You are given an array of integers, containing both +ve and -ve numbers. You need to find the two elements such that their sum is closest to zero. eg. Array [15, 5, -20, 30, -45] O/P should be 15, -20 Solution: Searching for two numbers Read More →