int absn = abs(n);
if( absn == 0 )
else if( absn == 1)
return (n < 0) ? (1/x) : x;
double temp = pow(x, absn/2);
result = temp*temp;
result = temp*temp*x;
return ( n < 0 )? (1/result) : result;
This problem is posted on Hackerrank as part of 20/20 Hack March 2014.
If you do not want to read the solution and you want to solve the problem on your own, Click on the link. If you want to know the solution for the problem, read on…
For example, if the given range is [1,5] the number of perfect squares in this range is 2 (including the lower and upper bounds)
1= 12 and 4 = 22
The obvious solution is to check if each number in the given range is a perfect square or not. This runs O(n) time. For a small range of numbers, this works fine. But for a big range, this takes a lot of time.
Can we improve this solution further?
We can improve this as follows.
First we find the square roots of lower bound and and upper bounds. The difference between them gives the required number.
For example consider the range [2,11]
sqrt(2) = 1.414
sqrt(11) = 3.316
If you round them off, and take the difference (3-1), it is 2 which is the required answer.
However we have to handle two special cases.
Case 1: Lower and upper bounds are same.
For example [4, 4]. In this case we have to check if the given number is a perfect square. If it is, output 1, otherwise output 0.
Case 2: If the lower bound is a perfect square.
In this case, we have to add 1 to the diff of square roots.
For example consider [4, 20]; rounded square roots are [2, 4]; the diff is 2. But there are 3 perfect squares in the given range (4, 9, 16).
In all the remaining cases, the number of perfect squares is the difference of the square roots.
Here is the C++ implementation for this problem.
We have to write a function to modify the existing array without using any extra space and return the new length.
The solution to this problem is similar to that of “Deleting all instances of a particular number from a given array“.
We have two indices, one which keeps track of the unique elements and the other iterates through all the elements. Each time we visit an element, we check if it matches with the recently added unique elements. If does not match, we add it to the unique elements, otherwise we ignore that element and move on to the next.
This approach runs in O(n) time and O(1) space. Moreover it iterates over the array only once.
Here is the C++ program which implements this.
A magician starts by arranging 16 cards in a square grid: 4 rows of cards, with 4 cards in each row. Each card has a different number from 1 to 16 written on the side that is showing. Next, the magician asks a volunteer to choose a card, and to tell him which row that card is in.
Finally, the magician arranges the 16 cards in a square grid again, possibly in a different order. Once again, he asks the volunteer which row her card is in. With only the answers to these two questions, the magician then correctly determines which card the volunteer chose.
Here is a simple program which demonstrates the use of library sort() routine to sort an array as well as a vector.