Given an integer, write a function that calculates ⌈7n/8⌉ (ceiling of 7n/8) without using division and multiplication operators.
We strongly recommend to minimize your browser and try this yourself first.
Method 1:
The idea is to first calculate floor of n/8, i.e., ⌊n/8⌋ using right shift bitwise operator. The expression n>>3 produces the same.
If we subtract ⌊n/8⌋ from n, we get ⌈7n/8⌉
Below is the implementation of above idea :
C++
// C++ program to evaluate ceil(7n/8)// without using * and /#include <iostream>using namespace std;int multiplyBySevenByEight(int n){ // Note the inner bracket here. This is needed // because precedence of '-' operator is higher // than '<<' return (n - (n >> 3));}// Driver codeint main(){ int n = 9; cout << multiplyBySevenByEight(n); return 0;}// This code is contributed by khushboogoyal499 |
C
// C program to evaluate ceil(7n/8) without using * and /#include <stdio.h>int multiplyBySevenByEight(unsigned int n){ /* Note the inner bracket here. This is needed because precedence of '-' operator is higher than '<<' */ return (n - (n >> 3));}/* Driver program to test above function */int main(){ unsigned int n = 9; printf("%d", multiplyBySevenByEight(n)); return 0;} |
Java
// Java program to evaluate ceil(7n/8)// without using * andimport java.io.*;class GFG { static int multiplyBySevenByEight(int n) { /* Note the inner bracket here. This is needed because precedence of '-' operator is higher than '<<' */ return (n - (n >> 3)); } // Driver code public static void main(String args[]) { int n = 9; System.out.println(multiplyBySevenByEight(n)); }}// This code is contributed by Anshika Goyal. |
Python3
# Python program to evaluate ceil(7n/8) without using * and /def multiplyBySevenByEight(n): # Note the inner bracket here. This is needed # because precedence of '-' operator is higher # than '<<' return (n - (n >> 3))# Driver program to test above function */n = 9print(multiplyBySevenByEight(n))# This code is contributed by# Smitha Dinesh Semwal |
C#
// C# program to evaluate ceil(7n/8)// without using * andusing System;public class GFG { static int multiplyBySevenByEight(int n) { /* Note the inner bracket here. This is needed because precedence of '-' operator is higher than '<<' */ return (n - (n >> 3)); } // Driver code public static void Main() { int n = 9; Console.WriteLine(multiplyBySevenByEight(n)); }}// This code is contributed by Sam007. |
Javascript
<script>// JavaScript program to evaluate ceil(7n/8) without using * and / function multiplyBySevenByEight(n) { /* Note the inner bracket here. This is needed because precedence of '-' operator is higher than '<<' */ return (n - (n>>3)); } /* Driver program to test above function */ let n = 9; document.write(multiplyBySevenByEight(n)); // This code is contributed by Surbhi Tyagi.</script> |
PHP
<?php// PHP program to evaluate ceil// (7n/8) without using * and function multiplyBySevenByEight( $n){ // Note the inner bracket here. // This is needed because // precedence of '-' operator // is higher than '<<' return ($n - ($n >> 3));}// Driver Code$n = 9;echo multiplyBySevenByEight($n);// This code is contributed by Ajit?> |
Output :
8
Time Complexity: O(1)
Auxiliary Space: O(1)
Method 2 (Always matches with 7*n/8):
The above method doesn’t always produce result same as “printf(“%u”, 7*n/8)”. For example, the value of expression 7*n/8 is 13 for n = 15, but above program produces 14. Below is modified version that always matches 7*n/8. The idea is to first multiply the number with 7, then divide by 8 as it happens in expression 7*n/8.
C++
// C++ program to evaluate 7n/8 without using * and /#include<iostream>using namespace std;int multiplyBySevenByEight(unsigned int n){ /* Step 1) First multiply number by 7 i.e. 7n = (n << 3) -n * Step 2) Divide result by 8 */ return ((n << 3) -n) >> 3;}/* Driver program to test above function */int main(){ unsigned int n = 15; cout<<" "<< multiplyBySevenByEight(n); return 0;}// This code is contributed by shivanisinghss2110 |
C
// C program to evaluate 7n/8 without using * and /#include<stdio.h>int multiplyBySevenByEight(unsigned int n){ /* Step 1) First multiply number by 7 i.e. 7n = (n << 3) -n * Step 2) Divide result by 8 */ return ((n << 3) -n) >> 3;}/* Driver program to test above function */int main(){ unsigned int n = 15; printf("%u", multiplyBySevenByEight(n)); return 0;} |
Java
// Java program to evaluate 7n/8 // without using * and /import java.io.*;class GFG{ static int multiplyBySevenByEight(int n) { // Step 1) First multiply number // by 7 i.e. 7n = (n << 3) -n // * Step 2) Divide result by 8 return ((n << 3) -n) >> 3; } // Driver program public static void main(String args[]) { int n = 15; System.out.println(multiplyBySevenByEight(n)); }}// This code is contributed by Anshika Goyal. |
Python3
# Python3 program to evaluate 7n/8 # without using * and /def multiplyBySevenByEight(n): #Step 1) First multiply number # by 7 i.e. 7n = (n << 3) -n # Step 2) Divide result by 8 return ((n << 3) -n) >> 3; # Driver coden = 15;print(multiplyBySevenByEight(n));#this code is contributed by sam007. |
C#
// C# program to evaluate 7n/8 // without using * and /using System;public class GFG { static int multiplyBySevenByEight(int n) { // Step 1) First multiply number // by 7 i.e. 7n = (n << 3) -n // * Step 2) Divide result by 8 return ((n << 3) -n) >> 3; } // Driver program public static void Main() { int n = 15; Console.WriteLine( multiplyBySevenByEight(n)); }}// This code is contributed by Sam007. |
Javascript
<script>// Javascript program to evaluate 7n/8 // without using * and /function multiplyBySevenByEight(n){ // Step 1) First multiply number // by 7 i.e. 7n = (n << 3) -n // * Step 2) Divide result by 8 return ((n << 3) -n) >> 3;}// Driver codevar n = 15;document.write(multiplyBySevenByEight(n));// This code is contributed by shikhasingrajput </script> |
PHP
<?php// PHP program to evaluate 7n/8// without using * and /function multiplyBySevenByEight( $n){ /* Step 1) First multiply number by 7 i.e. 7n = (n << 3) - n Step 2) Divide result by 8 */ return (($n << 3) -$n) >> 3;} // Driver Code $n = 15; echo multiplyBySevenByEight($n);// This code is contributed by anuj_67.?> |
Output :
13
Time Complexity: O(1)
Auxiliary Space: O(1)
Note : There is difference between outcomes of two methods. The method 1 produces ceil(7n/8), but method two produces integer value of 7n/8. For example, for n = 15, outcome of first method is 14, but for second method is 13.
Thanks to Narendra Kangralkar for suggesting this method.
Approach:
- Multiply the number n by 7 using the following steps.
- Left shift n by 3 positions (multiply n by 8).
- Subtract n from the result obtained in the previous step.
- To calculate the ceiling of 7n/8, add 7 to the result obtained in step 1.
- Right shift the result obtained in step 2 by 3 positions to divide it by 8.
Below is the implementation of this approach:
C++
#include <iostream>using namespace std;// Function to calculate ceil(7n/8) without using * and /int calculateCeiling(int n) { int result = ((n << 3) - n + 7) >> 3; return result;}// Driver codeint main() { int n = 9; cout << calculateCeiling(n) << endl; return 0;} |
Java
// Java code of the above approachimport java.util.*;public class GFG { // Function to calculate ceil(7n/8) without using * and / static int calculateCeiling(int n) { int result = ((n << 3) - n + 7) >> 3; return result; } public static void main(String[] args) { int n = 9; System.out.println(calculateCeiling(n)); }}// This code is contributed by Susobhan Akhuli |
Output:
8
Time Complexity: O(1), as it only involves a few bitwise operations regardless of the input value n.
Space Complexity: O(1) since it does not require any additional space that grows with the input size.
This article is contributed by Rajeev. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
