Program to find the product of a number with a Mersenne Number

Program to find the product of a number with a Mersenne Number

Given an integer N and a Mersenne number M, the task is to print their product without using the ‘*’ operator.
Note: Mersenne numbers are those numbers which are one less than a power of two.

Examples:

Input: N = 4, M = 15
Output: 60

Input: N = 9, M = 31
Output: 279

Approach: The given problem can be solved based on the following observations: 

Suppose M can be represented as 2X – 1, then the product of N with M can be represented as N · 2X – N.

Therefore, product of any Mersenne number with any number N can be represented as (N << log₂(M+1)) – N.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    long multiplyByMersenne(long N, long M) {               long x = log2(M + 1);             return ((N << x) - N); }    int main() {     long N = 4;     long M = 15;        cout << multiplyByMersenne(N, M);        return 0; }

Output:

60

Time Complexity: O(1)
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)