4
In this thread we use 32-bit signed integers (assuming the usual two's complement). For simplicity I shall call this type Int32. The range is from -2147483648 through 2147483647. Any two values can be successfully multiplied (the result is an Int32 as well) since we use multiplication without overflow checking (we only keep the 32 least significant bits of the product).
For example, we have:
2147483647 * 2 == -2
and so on.
If your language does not have native support for 32-bit signed integers (with two's complement), you must emulate it.
Your task is to solve the equation:
a * x == b
where a and b are given as input, and it is assumed that a is an odd number (i.e. least significant bit is 1). You output an Int32 value.
- The input to your program shall be two Int32 values
aandb, andawill be odd - The output must be one Int32 value such that (if we call the output
x)a*x == b - You do not have to handle invalid input; in particular, if the argument
ais an even number, it does not matter what your code does - Code golf
Test cases:
Input Output 1,42 42 3,126 42 5,5 1 -3,126 -42 3,-126 -42 -3,-126 42 2147483647,-2 2 2147483647,2 -2 2147483647,666 -666 3,0 0 3,1 -1431655765 3,2 1431655766 -387907419,1342899768 1641848792 348444091,1076207126 -1334551070 10,14 irrelevant (illegal input)
In the last case [a,b]==[10,14], even if there is a solution x = -1717986917 (not unique, x = 429496731 also works), you do not have to handle that case (10 is not odd).
Jeppe Stig Nielsen
Posted 2017-10-31T12:34:38.633
Reputation: 602
@PeterTaylor, is this an exact duplicate? The other thread takes in the "denominator" (which they call
a) and the modulus (which they callb) and asks you to find "1/a" modulob, stating the result in the interval0...(b-1). My question says input is a "denominator" (which I also calla) and a "numerator"b, and the modulus is always2**32, and I want the result "b/a" modulo2**32, representative in the interval(-2**31)...(2**31-1). I can see the threads are very related, but answers to one challenge cannot be used for the other. – Jeppe Stig Nielsen – 2017-10-31T14:09:52.060(continued) My question is actually much less general because I ask for only one magical modulus. And there are also different requirements when
– Jeppe Stig Nielsen – 2017-10-31T14:15:43.737ais not invertible modulo the relevant modulus. Addition: The other thread also links Compute modular inverse which is very similar. I admit I do not know just how similar to challenges must be to be considered duplicates, here on Code Golf.The basic rule of thumb is: could answers be copied across with only minor changes? Things like hard-coding a parameter or adding a loop over a parameter are considered sufficiently minor. The difference of range between
0...(b-1)and(-2**31)...(2**31-1)is completely trivial, because when working with 32-bit integers that just drops out. – Peter Taylor – 2017-10-31T14:51:17.297An answer such as the earliest one below, by HyperNeutrino, could never be copied to the other thread because the other thread requires arbitrary modulus, and HyperNeutrino's answer only works with modulus
2**32. However, in the opposite direction, most answer from the other thread can be copied to here, though you need to insert a new multiplication by mybmodulo2**32, but I suppose they would not "compete" well in here because they are designed to also be well-behaved in the case where the inverse is impossible. – Jeppe Stig Nielsen – 2017-10-31T15:59:32.500