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.

Solutions

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 10 months ago

Next > < Previous

Related Solutions

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...

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.

prove that there exist infinitely many primitive Pythagorean triples

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");...

Statement: For a given integer N, print all the squares of positive integers where the square...

Statement: For a given integer N, print all the squares of positive integers where the square is less than or equal to N, in ascending order. Programming Tasks: Prompt the user to input the value of N Output to the screen all squares of positive integers <= N Tests: Item Test 1 Test 2 Test 3 Inputs: 50 9 100 Outputs: 1 4 9 16 25 36 49 1 4 9 1 4 9 16 25 36 49 64 81...

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

Let X Geom(p). For positive integers n, k define P(X = n + k | X...

Let X Geom(p). For positive integers n, k define P(X = n + k | X > n) = P(X = n + k) / P(X > n) : Show that P(X = n + k | X > n) = P(X = k) and then briefly argue, in words, why this is true for geometric random variables.

Let f(x) = {(C/x^n if 1≤ x <∞; 0 elsewhere)} where n is an integer >1....

Let f(x) = {(C/x^n if 1≤ x <∞; 0 elsewhere)} where n is an integer >1. a. Find the value of the constant C (in terms of n) that makes this a probability density function. b. For what values of n does the expected value E(X) exist? Why? c. For what values of n does the variance var(X) exist? Why?

Subjects