An integer n is said to be Pythagorean if there exist two nonzero integers x and...

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.

Expert Solution

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.

venereology answered 2 years ago

The least common multiple of nonzero integers a and b is the smallest positive integer m...

The least common multiple of nonzero integers a and b is the smallest positive integer m such that a|m and b|m. It is denoted [a, b], or sometimes [a, b] for short. Prove the following: 1) If a|k and b|k, then [a, b]|k. 2) If gcd(a, b) = 1, then [a, b] =ab 3) If c >0,then [ca, cb] =c·[a, b]. 4) If a >0 and b >0,then [a, b] =ab / gcd(a, b).

A Pythagorean triplet is a set of positive integers (x, y, z) such that x2 +...

A Pythagorean triplet is a set of positive integers (x, y, z) such that x2 + y2 = z2. Write an interactive script that asks the user for three positive integers (x, y, z, in that order). If the three numbers form a Pythagorean triplet the script should a) display the message ‘The three numbers x, y, z, form a Pythagorean triplet’ b) plot the corresponding triangle using red lines connecting the triangle edges. Hint: place the x value on...

Two numbers a and b are called pythagorean pair if both a and b are integers...

Two numbers a and b are called pythagorean pair if both a and b are integers and there exists an integer c such that a2 + b2 = c2. Write a function pythagorean_pair(a,b) that takes two integers a and b as input and returns True if a and b are pythagorean pair and False otherwise.

For all integers n > 2, show that the number of integer partitions of n in...

For all integers n > 2, show that the number of integer partitions of n in which each part is greater than one is given by p(n)-p(n-1), where p(n) is the number of integer partitions of n.

The greatest common divisor of two integers x and y is the largest positive integer that...

The greatest common divisor of two integers x and y is the largest positive integer that evenly divides both. For example, gcd(12,6)=6, gcd(21,14)=7, gcd(31,10)=1, gcd(55,25)=5 Recall that the gcd of two integers is gcd(a,0) = a gcd(a,b) = gcd(b, a%b) Create int gcd(int x, int y). Assume that the two integers are zero or positive. Write the code as a pure function. Put it in a file gcd.c. Of course, you will need to test it. The function Φ(n) counts...

A positive integer n is said to be prime (or, "a prime") if and only if...

A positive integer n is said to be prime (or, "a prime") if and only if n is greater than 1 and is divisible only by 1 and n . For example, the integers 17 and 29 are prime, but 4, 21 and 38 are not prime. Write a function named "is_prime" that takes a positive integer argument and returns as its value the integer 1 if the argument is prime and returns the integer 0 otherwise. Can you make...

prove that there exist infinitely many primitive Pythagorean triples

Linear Algebra we know that x ∈ R^n is a nonzero vector and C is a...

Linear Algebra we know that x ∈ R^n is a nonzero vector and C is a real number. find all values of C such that ( In − Cxx^T ) is nonsingular and find its inverse knowing that its inverse is of the same form

Problem 5 Given a table of n integers and an integer k, make a program in...

Problem 5 Given a table of n integers and an integer k, make a program in C++ that: a) Read n b) Read the table of numbers. c) Determine the number of elements in the table less than k d) Determine the number of elements in the table equal to k e) Determine the number of elements in the table greater than k f) That displays the values found

Question Write a C program that asks the user to enter two integers x and n....

Question Write a C program that asks the user to enter two integers x and n. Then the program computes xn (=x * x * x …… (n times)) using for loop. and give me an output please use printf and scanf #include int main(void) { //Declare required variables //read two integers x , n from the keyboard //compute xn using for loop printf("< Your name >\n");...

Question