Prev   Next

Solve 7n By 8







"You must do the things you think you cannot do."

Solve 7n By 8

Welcome Back Reader!
In this article we will discuss the next problem based on 'Bit Manipulation' i.e. 'Solve 7n by 8'. This is a very exciting problem.
Before you move any further, it is advised that you give this problem a fair try.
Let's jump to the problem.

Important Links : our website , this problem ,

Understanding problem:

In this problem you are given a number n.
All you need to do is to calculate the value of 7n/8 without using division and multiplication.

For example:
Sample Input: 15
Sample Output: 13

How?
Well the answer would be = (7*15)/8 = 13.125
Since we are dealing in integers, we neglect the part after decimal, which gives us 13.

Approach :
Moving On:
  1. 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 multiplication and division.
  2. Mathematical analysis:
    => 7*N/8 = (8*N - N)/8
    => (8*N - N)/8 = (((N << 3) - N) >> 3)
  3. Here (N << 3) is a left shift to 3 positions and as we know that a left shift of bits is the same as multiplication of a decimal integer by 2 so shifting by 3 positions is the same as multiplying a number by 8.
  4. Mathematical proof for above statement is shown below for (57<<3):
    5. img
  5. After that we simply subtract N from this result which will result in 7*N in our numerator.
  6. As we know that right shift by a position is equivalent to division by 2 in the decimal number system so we need to divide the numerator by 8 so we will be shifting the numerator to right by 3 positions.
  7. Mathematical proof for above statement is shown below for (57>>3):
    8. img
  8. Now we can compute the above gained expression to get our result.

Let's try to code this!

img

Well, this was quite easy. Wasn't it?

For more clarity of this part, watch part of the video.

import java.io.*; import java.util.*; public class Main { public static void main(String[] args){ Scanner scn = new Scanner(System.in); int n = scn.nextInt(); //write your code here int val = (((n << 3) - n) >> 3); System.out.print(val); } }
java; true";
Analysis:
Time Complexity:

The time complexity for the function is constant.

Space Complexity:

The space complexity for the function is constant.

We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.

Trust me it will just get easier to understand after you have watched the solution video.You can contact us via our website. Doubts, suggestions and feedback are always welcomed.
It is also advised that you follow the sequence of modules and questions which is there on our website.
Keep practicing more and more problems daily. Meditate enough on each step of each problem.

All the best for an adventurous future!
Happy Coding!

Solve 7n By 8
Author: Nikita Aggarwal
 
Run
Id Name