Category Archives: C Programming

Count Total Set Bits in All Numbers From 1 to N

Problem: Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n. Examples: Input: n = 3 Output: 4 Input: n = 6 Output: 9 Input: n = 7 Output: 12 Input: n = 8 Output: 13 Solution: The solution is to run a Read More →

Find the Maximum of Two Numbers Without Using if-else

Find the maximum and minimum of two integers without branching i.e. if condition. Solution: Minimum of two numbers can be found from the following: Min(x,y) = y ^ ((x ^ y) & -(x < y)) It works because if x < y, then -(x < y) will be all ones, so r = y ^ Read More →

Find the Element that Appears Once

Problem: Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space. Examples: Input: arr[] = {10, 1, 10, 3, 10, 1, 1, 2, 3, 3} Output: 2 Solution: If O(1) space constraint was not Read More →

Dynamic Memory Allocation (Stack vs Heap)

Dynamic Memory Allocation

The Stack What is the stack? It’s a special region of your computer’s memory that stores temporary variables created by each function (including the main() function). The stack is a “LIFO” (last in, first out) data structure, that is managed and optimized by the CPU quite closely. Every time a function declares a new variable, Read More →

How to Check if a given Number is Fibonacci number?

In mathematics, the Fibonacci numbers or Fibonacci sequence are the numbers in the following integer sequence: 1,1,2,3,5,8,13,21,34,55,89,144.. A simple way is to generate Fibonacci numbers until the generated number is greater than or equal to ‘x’. Following is an interesting property about Fibonacci numbers that can also be used to check if a given number Read More →

Macros vs Functions

Macros are pre-processed which means that all the macros would be processed before your program compiles. However, functions are not preprocessed but compiled. See the following example of Macro: Output: 10 See the following example of Function: Output: 10 In short, Macro features: Macro is Preprocessed No Type Checking Code Length Increases Use of macro Read More →

Pascal’s Triangle

Given numRows, generate the first numRows of Pascal’s triangle. For example, given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] The logic becomes apparent just by looking at the pattern, but the property of pascal’s triangle comes from coefficients in the binomial expansion. nCk = n-1Ck + n-1Ck-1 and nC0 =1

Count Number of Bits to be Flipped to Convert A to B

Suppose, I have two numbers A and B. I need to find out how many numbers of bits needed to be changed to convert A to B. Like: A = 1101101 B = 1011011 ^^ ^^ Here, we need to change 4 bits to convert A to B How can I do this? Solution: 1. Read More →

Union and Intersection of two Linked Lists

Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Order of elments in output lists doesn’t matter. Following are simple algorithms to get union and intersection lists respectively. Intersection (list1, list2) Initialize result list as NULL. Traverse list1 and look for its Read More →

Given a triangle, find the minimum path sum from top to bottom

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = Read More →

Check Whether a Given Point Lies inside a Triangle or not

Given three corner points of a triangle, and one more point P. Write a function to check whether P lies within the triangle or not. The program needs to read the values of three coordinates A(x1,y1) B(x2,y2) C(x3,y3) as well as another coordinate P(x,y) and determine whether this point is inside a triangle formed from Read More →

Write Power Function without using multiplication(*) and division(/) operators

Write your own Power function without using multiplication(*) and division(/) operators? (Using Nested Loops) We can calculate power by using repeated addition. For example to calculate 5^4. 1) First 5 times add 5, we get 25. (5^2) 2) Then 5 times add 25, we get 125. (5^3) 3) Then 5 time add 125, we get Read More →