Question: Given an integer N, convert it into a string of words. Input: N = 345 Output: three hundred forty five This is one of the most common problems that we come across in out daily lives. We need to input a number from the user and print it in words. First, we perform a number of checks on the input string. If it is in any way invalid, the result is the empty string (“”). Next, we take note of whether or not the string begins with a ‘‘.…
Puzzle


Question: Given an integer N, find the prime numbers in that range from 1 to N. Input: N = 25Output: 2, 3, 5, 7, 11, 13, 17, 19, 23 We discussed the basic approaches to find the first N prime numbers in these posts Find the first N prime numbers (Method 1) Find the first N prime numbers (Method 2) It is advised that you go through the above posts to get a basic understanding of the approach that we have used to determine the prime numbers. Now lets analyze…

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 axisaligned 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 coordinates 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,…

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 1bit. 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…

Arrays
Given a function that generates random number from 17, write a function that generates random numbers from 110.
by nikoo28Question: You are given a function rand7() – that generates random numbers from 17. Write a function rand10() – that uses rand7() to generate random numbers from 110. 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[N1] and Output[1] will be multiplication of A[0] and from A[2] to A[N1]. 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…