|
Given two positive integer x and y. we have to find the value of y mod 2x. That is remainder when y is divided by 2x.
Examples:
Input : x = 3, y = 14
Output : 6
Explanation : 14 % 23 = 14 % 8 = 6.
Input : x = 4, y = 14
Output : 14
Explanation : 14 % 24 = 14 % 16 = 14.
To solve this question we can use pow() and modulo operator and can easily find the remainder.
But there are some points we should care about:
- For higher value of x such that 2x is greater than long long int range, we can not obtain proper result.
- Whenever y < 2x the remainder will always be y. So, in that case we can restrict ourselves to calculate value of 2x as:
y < 2x
log y < x
// means if log y is less than x, then
// we can print y as remainder.
- The maximum value of 2x for which we can store 2x in a variable is 263. This means for x > 63, y is always going to be smaller than 2x and in that case remainder of y mod 2x is y itself.
keeping in mind the above points we can approach this problem as :
if (log y < x)
return y;
else if (x < 63)
return y;
else
return (y % (pow(2, x)))
Note: As python is limit free we can directly use mod and pow() function
C++
<?php
function yMod($y, $x)
{
if ((log($y) / log(2)) < $x)
return $y;
if ($x > 63)
return $y;
return ($y % (1 << $x));
}
$y = 12345;
$x = 11;
echo (yMod($y, $x));
?>
|
Javascript
<script>
function yMod(y, x)
{
if ((Math.log(y) / Math.log(2)) < x)
return y;
if (x > 63)
return y;
return (y % (1 << x));
}
let y = 12345;
let x = 11;
document.write(yMod(y, x));
</script>
|
Time Complexity: O(x)
Auxiliary Space: O(1)
Approach: Bitwise manipulation
This approach is called bitwise manipulation. Here are the steps:
- Calculate 2^x using the left shift operator (<<). For example, 1 << 3 will give us 8.
- Subtract 1 from the result of step 1 to get a binary number with x number of 1’s. For example, 2^3 – 1 = 7, which in binary is 111.
- Perform a bitwise AND operation between y and the result of step 2. The result will be the remainder when y is divided by 2^x.
C++
#include <iostream>
int find_modulo(int x, int y)
{
int result = y & ((1 << x) - 1);
std::cout << "The remainder of " << y << " when divided by 2^" << x << " is " << result << "." << std::endl;
return result;
}
int main()
{
find_modulo(3, 14);
find_modulo(4, 14);
return 0;
}
|
Java
public class Main {
public static int find_modulo(int x, int y) {
int result = y & ((1 << x) - 1);
System.out.println("The remainder of " + y + " when divided by 2^" + x + " is " + result + ".");
return result;
}
public static void main(String[] args) {
find_modulo(3, 14);
find_modulo(4, 14);
}
}
|
Python3
def find_modulo(x, y):
result = y & ((1 << x) - 1)
print(f"The remainder of {y} when divided by 2^{x} is {result}.")
return result
find_modulo(3, 14)
find_modulo(4, 14)
|
C#
using System;
class Program {
static int FindModulo(int x, int y) {
int result = y & ((1 << x) - 1);
Console.WriteLine($"The remainder of {y} when divided by 2^{x} is {result}.");
return result;
}
static void Main(string[] args) {
FindModulo(3, 14);
FindModulo(4, 14);
}
}
|
Javascript
function findModulo(x, y) {
let result = y & ((1 << x) - 1);
console.log(The remainder of ${y} when divided by 2^${x} is ${result}.);
return result;
}
findModulo(3, 14);
findModulo(4, 14);
|
Output
The remainder of 14 when divided by 2^3 is 6.
The remainder of 14 when divided by 2^4 is 14.
The time complexity: O(1)
The auxiliary space: O(1)
Compute modulus division by a power-of-2-number
|
