Hello, I need explenation about GCD programm, c++

Question

Hi, can someone give me breakdown of this code, specificly about functions and how they work on this program, also line 36 (int n = sizeof(arr) / sizeof(arr[0]);) why is it important and what does it do.? Ty for your time and sorry for any grammar mistakes :)

code:

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}

int findGCD(int arr[], int n)
{
int result = arr[0];
for (int i = 1; i < n; i++)
{
result = gcd(arr[i], result);

if(result == 1)
{
return 1;
}
}
return result;
}

int main()
{

int number;
cin >>number;
int arr[number];
for (int i=0;i<number;i++){
cin >> arr[i];
}
int n = sizeof(arr) / sizeof(arr[0]);
cout << endl;
cout << findGCD(arr, n) << endl;

if (findGCD(arr, n)%2==1) cout << "Yes";
else cout << "No";
return 0;
}

Answer 1

Dr. Alien

No problem 👍 sorry for the long explanation.

But it is best to try and analyze the code first and ask what you dont understand after analyzing it,and not ask the whole breakdown of the code :)

Answer 2

Dr. Alien

Int gcd function

The first gcd function is the formula to search the greatest common divisor,the formula is, it gets two arguments a and b,checks if the a is equals to 0,if it is return b,but if its not,it calls itself again now using the result of b modulo(%) a as the a argument,and a as the b argument,then repeat the if statement check.

The find gcd function is to find the gcd in an integer array, it has 2 arguments, the int array and n variable which is length of the array.

It defines a result variable which has the value of index 0 in the array argument,iterates over the length of the n variable starting from 1,and calls the first gcd function using the value of index [current iteration] of the array as the A argument, and the index 0 value of array as the B argument, and stores the result back to the result variable.

See my next comment for the follow up of this explanation

Answer 3

Dr. Alien

If result is now equals to 1 return 1,else it keeps going with the for loop until it finishes,then return the value index 0 of array which is in result if it is never equals to 1.

The int main function, gets an input from user for what size/length does the user want for the array,then iterates over that so the user can input values in the range of that length.

Int n can be used here,but using the number variable also works because that is the length the user wants for the list.

Then it calls the findgcd function,print the result out,and an if statement to check if the result of findgcd modulo by 2 is equals to 1,if it is print yes,if not print no.

Int n is basically getting the length of the list through the sizeof function , and divides it with the first element of the array,because sizeof calculates every element in the array by its byte value,in this case int has 4 byte value,so after getting the sizeof, it needs to be divided with 4 bytes again to get the real size.

Answer 4

I think the best way is first closing this tutorial on SoloLearn. With that all your questions will be answered.

Answer 5

Thank You sir, that helps.