In: Computer Science
An integer n is said to be Pythagorean if there exist two nonzero integers x and y such that x2 + y2 = n2 . Present an O(n) time algorithm to check if a given integer n is Pythagorean or not. Assume that you can nd the square root of any number in O(1) time.
def isPythagorian(n): 1. Take 2 variables, left and right. 2. initialize left with 1 and right as n. 3. While left <= right, Keep doing below: 3.1. Find the squared sum ss of left and right as: ss = left**2 + right**2 3.2 if ss is same as n, Then Yes, The output that given number is pythagorean and end. 3.3 Else if ss is less than n, Then increment left by 1 3.4 Else if ss is more than n, Then decrement right by 1. 4. Output that number is not a pythagorean number. 5. End.
this algorithm is an O(N) algorithm, Since We take 2 variables left and right.. Left goes from 1 to N, while right goes from N to 1, till the time they do not cross each other.. Since, In each time unit, we are covering one unit towards left or to right, Hence For a number N, it is a O(N) algorithm.
************************************************** Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.
Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.