Math Prorgramming Interview Question

[DominiConnor]

Here's one to puzzle over

given two numbers x,y I want to find out if their product is too large to work with the numeric type I'm using.

Like all good interview questions, it scales...

So given N numbers, how do I work out whether their product gets outside the range ?

 

[Mr Doe]

This is how I would do it. First let there only be (x,y). I assume WLOG that they are both positive, and that I know the upper bound (L^{up}). If they are both negative, then it doesn't matter (product positive), if only one is negative, then I would work with lower bound (L^{down}).
First, I assume that one of the numbers is an integer, let it be (x). If (x) or (y) is greater than (L^{up}), product is too large. If not, I can add one (y), leaving me with ((x-1)) to go. Then I check ((0<)L^{up}-y<y), if its true, I can add two of (y) leaving me with ((x-2)). Again, I check ((0<)L^{up}-2y<y), if true then I can add three of (y), leaving me with ((x-3)), if not true, product is larger than the upper bound. So, I continue further, if ((0<)L^{up}-(x-1)y<y), I can add exactly (x) of (y), and still not break the upper bound, so the product is not too large, if the inequality is not true, product is too large.
Let (x) be positive rational, I can write it as (x=x_{\mathbb{N}}+x_{\mathbb{Q}}), where (x_{\mathbb{Q}}), is smaller than one, using the previous algo I check if the product for the integer part of (x) is to large, if it's not too large, I finally check ((0<)L^{up}-x_{\mathbb{N}}y<x_{\mathbb{Q}}y), if it's true, my product is not out of range, hence I can add (x_{\mathbb{N}}y + x_{\mathbb{Q}}y=xy) and still be below (L^{up}).
If I have N numbers (x_1,\dots,x_n), take first two, and use the previous algo ((x=x_1,y=x_2)), if bellow the upper bound then take third, and use the algo for (x=x_1x_1, y=x_3), etc.

And now the interesting part, I have two numbers, what if one of the numbers is greater than the upper bound, but the other one is very small, so their product should be bellow the upper bound? I must admit I'm don't have a good idea. I should think a bit more about it.

 

[tobias elbert]

I think the way to go about this is to look at x's and y's binary representation which renders the problem to one where one considers the bit lengths of x and y, say n and m. The product of their numeric types will have some bit representation of n + m bits length. If n + m is greater than the maximum number of bits reserved for the corresponding numeric type, then the product of the numeric types (x * y) will be too large.

 

[dearappu]

If I have a computer and whatever programming language I am using..

just do this:

z = x * y

z is defined as the same numeric type as x and y

at this point if the product is above the range of the numeric type,

then z stores some number unrelated to the actual product of x and y after overflowing

and all

then do

IF((z/x) = y) is TRUE then my numeric type is good to store the product of x and y

Please correct in case of error

 

[Springer]

^ I'm wondering if that will compile though?

Why not find the type limit and store it in say [z]
Then for any values [x,y] type cast their absolute product to an able type and do a comparison with [z], if it's smaller, great, otherwise there's a problem

 

[Amaan]

I liked the binary representation idea...but is there a straight forward way of doing that?

just thinking out-loud:

if we know the max, can't we just use "log"s? i.e.,

log x + log y < log max ==> xy < max

any ideas on this?

 

[tobias elbert]

I liked the binary representation idea...but is there a straight forward way of doing that?

just thinking out-loud:

if we know the max, can't we just use "log"s? i.e.,

log x + log y < log max ==> xy < max

any ideas on this?

Thought about this as well and I reckon this should work also. Unless x or y > max and such that their product is < max, as another poster pointed out.

 

[iddqd]

If I have a computer and whatever programming language I am using..

just do this:

z = x * y

z is defined as the same numeric type as x and y

at this point if the product is above the range of the numeric type,

then z stores some number unrelated to the actual product of x and y after overflowing

and all

then do

IF((z/x) = y) is TRUE then my numeric type is good to store the product of x and y

Please correct in case of error

This seems like the best solution to me so far, I think other people are ignoring that the numbers usually wrap around so doing a comparison to the max will not be meaningful. I implemented it for n numbers here. (Recall the use of the vector constructor here means 5 copies of each number... INT_MAX is around 4.2 billion for 32-bit signed integers. 100^5 should end up being a number that starts with 1 and has a lot of 0s behind it, which you should see isn't the case when you run this.)

#include <iostream>
#include <vector>
using namespace std;
bool checkproduct (vector<int> multipliers);
int main()
{    
     cout << "INT MAX is " << INT_MAX << endl;
    
    vector<int> goodmultipliers(5, 2);
    vector<int> badmultipliers(5, 100);
    
    if (checkproduct(goodmultipliers) == 1) {
       cout << "Product is valid" << endl;
    } else {
      cout << "Product is not valid" << endl;
    } 
    if (checkproduct(badmultipliers) == 1) {
       cout << "Product is valid" << endl;
    } else {
      cout << "Product is not valid" << endl;
    } 
    
    system("PAUSE");
    
    return 0;   
    
}
bool checkproduct (vector<int> multipliers)
{
    int product = 1;
     
    for (int i = 0; i < multipliers.size(); i++)
    {
        product *= multipliers[i];        
    }
    
    cout << "Product is: " << product << endl;
    for (int i = multipliers.size() - 1; i >= 0; i--)
    {
        product /= multipliers[i];        
    }    
    
    return (product == 1);  
          
}

 

[alain]

I think Dominic meant to find out without doing the multiplication, but I might be wrong.

Also, don't assume a specifi numeric type (i.e. int).

 

[Mr Doe]

I'm going to give a critque of the methods mentioned.

Tobias has a nice approach, but it's restrictive in a way that it forces the bound to be in a binary form (i.e. (L=2^p,p\in\mathbb{N}), or maybe (2^p-1)), now that isn't such a problem if you want the (upper) bound to be 1000, so you say, what the hell, lets make it 1024, but if you want the bound to be (2^{1000}+1), going for (2^{1001}) would be a big issue. Also, it can be just plain wrong. Suppose, your upper bound is 8 (so anything less or equal than 8 goes, that is 4 bits), you take (x=1,y=8), x has 1 bit, y has 4 bits, together 5 bits, so you would say: wow, thats out of range. Another simple example, upper bound still 8 (4 bits), (x=3,y=3), x has 2 bits, y has 2 bits, so their product has 4 bits, so you would say; you're not out of range .

Dearapppu and iddqd assume system/language specifics, that is, if the product is out of range, that the number being stored will be unrelated to the actual value. Still assume, that the upper bound is 8, but my system can hold numbers up to (2^{32}), I take, x=5 and y=2, their product would be 10 (out of range), but dividing 10 by either x or y, would give me the correct value.

Amaan has a very good idea, but its not correct. Assume, upper bound (L^{up}), lower bound (L^{down}), take x and y really small, but positive (x,y\approx 0) so their product in fact would be bellow the upper bound. Taking logarithm of x and y, you could break the lower bound, because (\operatorname{ln}(x \text{ or} y)) go negative, so logaritam of any one of them can break the lower bound and you would be out of range. If, they alone don't break the lower bound, when you sum them, again you can break the lower bound, where in fact you are only concerned if their product doesnt break the upper bound cause both numbers are positive..

 

[iddqd]

Well, I just used signed integers in C++ as an example, since they're easy to work with and understand. I think the way Dominic states the problem that he means it is "closed', i.e. if I have N numbers of type x, their product should also be type x, and I can't use some other larger type as a way to check my results. (using "10" when your upper bound is 8 is implicitly using a larger type, and is cheating).

Re: Alain, If we're not allowed to use multiplication to check, then that is a bit more challenging.

 

[Amaan]

For the 'log' approach, to avoid the problem with x,y << 1, you can simply check if x,y<1 and then proceed:
if at least one of them is less than one, (and assuming that both x,y < max which I think can be assumed from the problem) , then we're fine
(no need to worry about log(x) tending to -inf)

if both are >1 then , then we take 'log' and check if log(x) + log(y) < log(max)

 

[Springer]

I think a very simple solution works fine, why make it more difficult?

[C# pseudocode]

class Program
    {
        static Int16 x, y;

        static void Main(string[] args)
        {
            ///ask for (x,y)
            Console.Write("enter integer x: ");
            x = Convert.ToInt16(Console.ReadLine());
            Console.Write("enter integer y: ");
            y = Convert.ToInt16(Console.ReadLine());

            //Is their product too large for this size?
            Console.WriteLine(IsSizeOk(x, y).ToString());

            Console.Read();
        }

        static private bool IsSizeOk(Int16 x, Int16 y)
        {
            //The Int16 value type represents signed integers
            //with values ranging from negative 32768 through
            //positive 32767.

            //so we cast the product to something bigger, say double
            double z = Math.Abs(x * y);

            //is size fine
            return (z < 32767) ? true : false;
        }

 

[pathfinder]

this should solve the problem...this will work for any data type int,float,char ....etc

#include<iostream.h>
#define SIZE(x) (sizeof(x)/sizeof(x[0]))
template <class t>
int checkrange(t* a ,int n){
        t z=1;
        
        for(int i = 0 ; i< n; i++)
        {
         z=a[i]*z;
         if(a[i] == 0) return 1;
        }
         
        for(int i=1;i<n;i++){
                 z=z/a[i];
        }
        if(z == a[0]) 
        {
        return 1;
        }
        else
        {
             cout<<"out of range...\n";
             return 0;
        }
        
}
        
        
        int main()
        {
            
            int x[]= {0xff456790,34,56,78};
            unsigned char a[]= {45,0x5};
            checkrange(x,SIZE(x));  //check for integer array -> this will give out of range error
            checkrange(a,SIZE(a));  //check for char array-> this is within range  
            
            }

 

[iddqd]

this should solve the problem...this will work for any data type int,float,char ....etc

just had a play with this.. very nice