Solve 7n By 8
1. You are given a number n.Input Format
2. You have to calculate the value of 7n/8 without using division and multiplication.
A number nOutput Format
Check the sample ouput and question video.Question Video
1 <= n <= 10^9Sample Input
15Sample Output
13
-
Editorial
The problem here deals with solving a particular expression of the type 7*N/8 using bit manipulation only i.e. we are not allowed to use mathematical tools such as multiplication or division.
Mathematical analysis:
=> 7*N/8 = (8*N - N)/8
=> (8*N - N)/8 = (((N << 3) - N) >> 3)
Here (N << 3) is a left shift to 3 positions and as we know that a left shift of bits is same as multiplication of a decimal integer by 2 so shifting by 3 positions is same as multiplying a number by 8. Now we simply subtract N from this result which will result in 7*N in our numerator.
Now as we know that right shift by a position is equivalent to division by 2 in decimal number system so as we need to divide the numerator by 8 so we will be shifting the numerator to right by 3 positions.
Here we just need to compute the above gained expression to get our result.
Time Complexity: O(1)
The time complexity for the function is constant.
Space Complexity: O(1)
The space complexity for the function is constant.
-
Asked in Companies
-
Related Topics