Solve 7n By 8

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a number n.
2. You have to calculate the value of 7n/8 without using division and multiplication.
Input Format 
A number n
Output Format 
Check the sample ouput and question video.
Question Video
Constraints 
1 <= n <= 10^9
Sample Input 
15
Sample 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






Video Solution

Code Solution

Run
 
Run
Id Name