Greatest common diviser of an arrray using divide conquer technique

user_13403510 0
Viewed 316

I am trying to find the GCD/HCF of an array, I know to write the function that finds the GCD of two numbers using Euclid's algorithm. so to find the GCD of the array I thought to use this Euclid algorithm as a divide and conquer technique for GCD arrays. I'm successfully able to divide it but stuck with the merge function to again do the GCD operation, I'm looking for help for the merge function in such cases i.e conquer part.

my code for it is as;

#include <iostream>
using namespace std;
long long GCD(long long  m,long long n)
{
    while(m%n!=0)
    {
        long long next_m=n;
        long long next_n=m%n;
        m=next_m;
        n=next_n;
    }
    return n;
}
//define merge function.
long long hcf_arr(long long *arr,long long start,long long end){
    if(end-start+1==2){
        return GCD(arr[start],arr[end]);
    }
    else{
        long long *u;
        u=new long long[(end-start+1)/2];
        long long *v;
        v=new long long[(end-start+1)-(end-start+1)/2];
        for(long long i=start;i<=(end-start+1)/2;i++){
            u[i]=arr[i];
        }
        for(long long i=(end-start+1)/2+1;i<=(end-start+1);i++){
            v[i]=arr[i];
        }
        hcf_arr(u,start,(end-start+1)/2);
        hcf_arr(v,(end-start+1)/2+1,end-start+1);
        //Merge function

    }

}

int main() {
    
}
divide-and-conquer recursion function arrays c++
2 Answers

You can find the GCD of the left and right subbarrays and compute the GCD of those two. This works because GCD of a list of numbers remains the same if you replace any number with its GCD w.r.t any of the subarrays containing that number.

FYI there is a nice one-liner for this std::reduce(arr.begin(),arr.end(),arr[0],GCD);.

Couple of points:

  1. I see unequal amount of new and delete statements, that is not good. Use std::vector.
  2. Those for loops can be replaced with std::copy
  3. Previous two steps can be combined with std::vector's range-based ctor.
  4. Since you are not modifying the arrays, mark them as const.
user_76917290

Just find GCD of the results (GCD of array would be GCD of GCDs of left and right half of the array).

    ...
    long long leftGCD = hcf_arr(u,start,(end-start+1)/2);
    long long rightGCD = hcf_arr(v,(end-start+1)/2+1,end-start+1);
    return GCD(leftGCD, rightGCD); //Merge function
} ...
user_53579860
Related