SP8547 MAIN74 - Euclids algorithm revisited

Consider the famous euclid algoithm to calculate the GCD of two integers (a, b): ``` int gcd(int a, int b) { while (b != 0) { int temp = a; a = b; b = temp % b; } return a; } ``` for input (7, 3) the 'while' loop will run 2 times as follows: (7, 3) => (3, 1) => (1, 0) Now given an integer N you have to find the smallest possible sum of two non-negative integers a, b (a >= b) such that the while loop in the above mentioned function for (a, b) will run exactly N times.

N/A

N/A