The HCF() function is used to find the HCF of two entered integers using recursion. In this C Program, we are reading the two integer numbers using ‘ a’ and ‘ b’ variable. The above program for finding HCF of two numbers has a time complexity of O(min(n1,n2)), as the for loop runs for minimum of number of times of n1 and n2.
Now, break the condition i.e., come out of the for loop and print the value of HCF. Inside if statement assign the value of i to variable HCF. 
Check for i=5, so 10%5=0 and 15%5=0 so, enter the if condition.
Repeat this step until if condition becomes true. At the beginning i = 1, 10%10 gives the remainder as 0 but 15 %10 is 5 so, the if condition is false, decrement the value of i to 9 and again check the if condition. Run the for loop from i = min to 1 and check if i divides both n1 and n2 completely. Find minimum of the two numbers and store it in the variable min i.e., min=10. Consider the two numbers are n1=10 and n2=15. So, the 1st greatest number that divides both the number completely is the HCF of the two numbers.) 
(We are breaking the for loop because we are checking for HCF from the greatest number possible for HCF. Divide both the numbers n1 and n2 by i, if both gives remainder = 0 then store the value of i in HCF variable and break the for loop. Run the for loop from i=min to i>=1 and decrease the value of i by 1 after each iteration.Ĥ. Store the minimum of the two integers in the variable min.ģ. Take the two integers n1 and n2 as input.Ģ. All the variables initialized takes a constant O(1) space.ġ. In the above program, space complexity is O(1) as no extra variable has been taken to store the values in the memory.
The above program for finding HCF of two numbers has a time complexity of O(log(min(a,b))), as the while loop runs for number of times the numerator is divided by the denominator.
Now, check the while loop condition again, this time remainder = 0, therefore come out of the loop and store the value of the denominator in hcf i.e., hcf = 10. Calculate the remainder of the two variables i.e., remainder = 20%10 = 0. Now, assign the value of the denominator to the numerator and the value of the remainder to the numerator i.e., numerator=20 and denominator=10. Divide the numerator by the denominator and store the value in the remainder variable i.e., remainder = 30%20 = 10. Now, assign the value of the denominator to the numerator and the value of the remainder to the numerator i.e., numerator=30 and denominator=20. Now, enter the while loop and check if the remainder value is ‘0’ or not. Divide the numerator by the denominator and store the value in the remainder variable i.e., remainder = 50%30 = 20. Consider, the two numbers 50 and 30, first find the greater of the two numbers and store the greater in the numerator and smaller in the denominator i.e., numerator=50 and denominator=30.
0 kommentar(er)
