Given a number N and a sorted array A, check if there are two numbers in A whose product is N

user_16292414 0
Viewed 391

Given a number N and a sorted array A, design an algorithm - using the Divide and Conquer approach - to check if there exist index i and index j such that A[i]*A[j] == N (return 1 if present, 0 if not).

I'm having a hard time proceeding in the required (recursive) way. I think I figured out only a part of one possible solution, but even there I'm not a 100% sure if it's correct: I thought that if the product between the first element and the central element of the array is greater than N, then the numbers I'm looking for (if present) are certainly in the first half of the array, so I can recursively call the function on that part, like so (I'm using C):

int productN(int A[], int i, int j, int N){

    // missing base case

    int m = (i+j)/2;
    
    if(A[i]*A[m] > N){
        return productN(A, i, m, N);
    } else{
        // do something else
    }
}

int main(){

    int A[]={1, 2, 3, 4, 5};
    printf("%d\n", productN(A, 0, 4, 15));  // initial value for i and j are the first and last index of the array

    return 0;

}

Apart from that, I'm stuck, I can't even think of a base case, so any help will be greatly appreciated, thanks.

Edit: Based on your very helpful answers, using binary search, I think I got it:

int productN(int A[], int i, int j, int N){
    
    int m = (i+j)/2;    // central element of the current array
    
    int x;
    for(x=i; x<=m; x++){
        if(N%A[x]==0 && binarySearch(A, m, j, N/A[x]))
            return 1;
    }
        
    if(i!=j){
        if(productN(A, i, m, N) || productN(A, m+1, j, N))
            return 1;
    }
    
    return 0;

}

Is it good? Can it be better?

Edit: it's been a while now since I asked this question, but I wrote another solution, simplier to read. I'll leave it here in case anyone is interested.

int productN(int A[], int i, int j, int N, int size){
    
    if(i==j){        // base case
        if(N%A[i]==0)
            return binarySearch(A, 0, size-1, N/A[i]);
        else
            return 0;
    }
        
    int m = (i+j)/2; 
    
    if((N%A[m])==0){
        if(binarySearch(A, 0, size-1, N/A[i]))
            return 1;
    }
    
    return productN(A, i, m, N, size) || productN(A, m+1, j, N, size);

}
divide-and-conquer recursion c arrays algorithm
1 Answers

Using Divide and Conquer, you can use an approach similar to merge sort algorithm. As the comments suggest, there are easier approaches. But if Divide and Conquer is a must, this should suffice.
(I'm not proficient in C, so I'll just write the algorithm)

def productN(arr):
    x = len(arr)
    left_half = arr[0:x/2]
    right_half = arr[x/2:]
    if productN(left_half) or productN(right_half):
        return True
    for i in left_half:
        if N%i==0 and binary_search(right_half, N/i):
            return True
    return False
user_93507200
Related