Bit Hacks – Part 1 (Basic)
In this post, we will see how to 1. Check if an integer is even or odd, 2. Detect if two integers have opposite signs or not, 3. Add one to an integer, 4. Swap two numbers without using any third variable.
Tag: Easy
Efficiently implement power function – Iterative and Recursive
Given two integers, x and n, where n is non-negative, efficiently compute the power function pow(x, n) using Divide & Conquer.
Find the number of 1’s in a sorted binary array
Given a sorted binary array, efficiently find the total number of 1’s in it.
Find floor and ceil of a number in a sorted integer array
Given a sorted integer array, find the floor and ceil of a given number in it. The floor and ceil map the given number to the largest previous or the smallest following integer.
Recursive program to print reverse of a string
Given a string, print it backwards using recursion.
Find the first or last occurrence of a given number in a sorted array
Given a sorted integer array, find the index of a given number’s first or last occurrence. If the element is not present in the array, report that as well.
Find the number of rotations in a circularly sorted array
Given a circularly sorted integer array, find the total number of times the array is rotated. Assume there are no duplicates in the array, and the rotation is in the anti-clockwise direction.
Exponential search
Given a sorted array of n integers and a target value, determine if the target exists in the array or not in logarithmic time. If the target exists in the array, print an index of it.
Interpolation search
Given a sorted integer array and a target, determine if the target exists in the array or not using an interpolation search. If the target exists in the array, print an index of it.
Binary Search Algorithm – Iterative and Recursive Implementation
Given a sorted array of n integers and a target value, determine if the target exists in the array or not in logarithmic time using the binary search algorithm. If target exists in the array, print the index of it.
Count negative elements present in the sorted matrix in linear time
Given an M × N matrix, which is row-wise and column-wise sorted, count the total number of negative elements present in it in linear time.
In-place rotate matrix by 90 degrees in a clockwise direction
Given a square matrix, rotate the matrix by 90 degrees in a clockwise direction. The transformation should be done in-place and in quadratic time.