nikoo28

Question: Given an integer N, find the prime numbers in that range from 1 to N. Input: N = 25 Output: 2, 3, 5, 7, 11, 13, 17, 19, 23 We discussed the most basic approach to find the first N prime numbers in this post. Find the first N prime numbers. (Method 1) Please go through the post if you are not familiar with the naive methods. They are necessary to learn how the code can be optimized further. So let us try to further optimize the previously discussed…

Question: Given an integer N, find the prime numbers in that range from 1 to N. Input: N = 25 Output: 2, 3, 5, 7, 11, 13, 17, 19, 23 Today let us discuss about a very common but very interesting problem “To find prime numbers in first N Natural numbers “. I will be taking here a very specific approach of first giving definition of prime numbers , using that definition to derive the algorithm, and then using different properties or results that can be further applied to our…

Question: You are given two axis-aligned rectangles. You have to determine if these rectangles overlap each other or not. Rectangle 1 : P1 (x, y), P2 (x,y) Rectangle 2 : P3 (x,y), P4 (x,y) In this problem statement, we are given co-ordinates for 2 rectangles and we have to determine if they overlap or not. In a way we can say that our use case looks like this. At the first glance, the problem seems to look very complicated. If you are coming up with a complicated set of conditionals,…

Question: Given an unsigned Integer, you need to reverse its bits. There are several methods of reversing the bits of an unsigned integer. Here, we devise an algorithm using the XOR swap trick. Hint: How do you swap the ith bit with the jth bit? Try to figure out if you could use the XOR operation to do it. The XOR swap trick: Reversing bits could be done by swapping the n/2 least significant bits with its most significant bits. The trick is to implement a function called swapBits(i, j),…

Question: Given an Integer, you need to determine if it is a palindrome or not. You should not use any extra space in the process. Input: 121 Output: Palindrome At the first go, the problems seems very easy to solve. We just need to reverse the number and check if it remains the same. Right? Don’t be deceived by this problem which seems too easy. Also note the restriction of doing it without extra space. We also need to think of a generic solution that is not language/platform specific. First,…

Here we will discuss the easiest and most simple way to change case of alphabets. Hint : We will be using bit hacks. Often during our programming needs we need to change the case of alphabets. This can be a problem requirement or simply our need to solve the question. There are several ways to do it, but what can be more beautiful than using bit hacks for the same. We discusses some of the BIT Hacks in these posts:- Low Level Bit Hacks Some advanced Bit Hacks Here I…

Here we shall discuss some high level Bit hacks that if used cleverly can really speed up your program execution time. We discussed some of the basic hacks in this post:- Low level bit hacks you must know. Please go through the post to get a little understanding of how the things work. Smart learners are anyways welcome to proceed. ;-) BIT HACK 6: Turn off the rightmost 1-bit. Now it finally gets more interesting!!! Bit hacks #1 – #5 were kind of boring to be honest. This bit hack…

Here we shall discuss some very low level Bit hacks that can really speed up your program execution time when used effectively. Every now and then we see bit level operators. Bit hacks are ingenious little programming tricks that manipulate integers in a smart and efficient manner. Instead of performing some operation (such as counting the 1 bits in an integer) by looping over individual bits, these programming nuggets do the same with one or two carefully chosen bitwise operations. To get things going I’ll assume that you know what…

Question: You are given a function rand7() – that generates random numbers from 1-7. Write a function rand10() – that uses rand7() to generate random numbers from 1-10. This appear to be one of those probabilistic analysis questions. You should be familiar with the concept of expected value, as it could be extremely helpful in probabilistic analysis. Hint: Assume you could generate a random integer in the range 1 to 49. How would you generate a random integer in the range of 1 to 10? What would you do if…

Question: There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. Solve it without division operator and in O(n). For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Array 1: {4, 3, 2, 1, 2} Output: {12, 16, 24, 48, 24} Since the complexity required is O(n), the obvious O(n2) brute force solution is not good…