Category: Algorithms
-
Data Structures & Algorithms – Dynamic Programming – Climbing Stairs
Problem: Given a step number in a stair case , find the number of ways you can reach that step in the staircase if you can make 1 or 2 steps at a time Input: 4 Output: 5 ways Since you can take any of the below sequence of steps: [1,1,1,1] , [1,2,1],[1,1,2] ,[2,1,1], [2,2]…
-
Data Structures & Algorithms in Java – Binary – Reverse Bits
Problem: Given a number , reverse the bits in that number Input: 00000010100101000001111010011100 Output: 00111001011110000010100101000000 Since in Java the above binary number will be represented as an integer , the output should be 964176192 which is the decimal equivalent of the above binary number Assumptions: The input is stored in 32 bits (which is the…
-
Data Structures & Algorithms in Java – Binary – Missing Number
Problem: Given an array with values between 1 to n , find the missing number between 1 to n that is not present in the array Input: [9,6,4,2,3,5,7,0,1] Output: 8 In the above array of length 9 we have all the numbers from 1 to 9 except 8 , so output is 8 Try out…
-
Data Structures & Algorithms in Java – Binary – Counting Bits
Problem: Given an integer , find the number of 1 bits for every number (in binary form) starting from 0 to that integer. Input: 8 Output: [0,1,1,2,1,2,2,3,1] For the number 8 , you need to find the number of 1 bits in the numbers 0,1,2,3,4,5,6,7,8 and store them in an output array in their respective…
-
Data Structures & Algorithms in Java – Binary – Number of 1 bits in an integer
Problem: Given an integer , count the number of 1 bits in it when converted to a binary Input: 8 Output: 1 (since the binary representation of 8 is 1000 and it has a single 1 bit) Try out the solution here: https://leetcode.com/problems/number-of-1-bits/ Solution: One way to solve this problem is to do AND operation…
-
Data Structures & Algorithms in Java – Binary – Sum of two integers
Problem : Given two integers, add them without using + and – operators. Input: a = 3 b= 5 Output: 8 Try out the solution here: https://leetcode.com/problems/sum-of-two-integers/ Hint: Use bitwise operators Solution: Let’s solve the problem using bitwise operators XOR, AND and SHIFT. Adding two binary numbers is equal to performing XOR operation between them…
-
Data Structures and Algorithms – Arrays – Container with Most Water
Problem: Given an array of heights representing the ends of a container , find the container with the maximum area. For example: Consider the below input: Input: height = [1,8,6,2,5,4,8,3,7] The height can be represented pictorially as below: Each line represents each height in the array in the order of the indices. You can join…
-
Data Structures and Algorithms in Java – Arrays – Three sum
Problem: Given an array of integers , find out triplets in the array such that their sum is 0. Constraints: There should not be any duplicates. Same number should not be added to itself. Assumptions: The array contains a minimum of 3 elements and maximum 3000 elements Numbers can vary from -100000 to 100000 Input:…
-
Data Structures and Algorithms in Java – Arrays – Search in Rotated Sorted Array
Problem: Given an array of integers which is sorted and rotated , find out if the given element is in the array or not. A rotated array is an array whose elements are shifted towards the beginning from the end. For example , consider the array: input = [1,2,3,4,5] If this array is rotated once…