Question

In: Computer Science

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.


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
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");...
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
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...
Let A[1..n] be an array of distinct positive integers, and let t be a positive integer....
Let A[1..n] be an array of distinct positive integers, and let t be a positive integer. (a) Assuming that A is sorted, show that in O(n) time it can be decided if A contains two distinct elements x and y such that x + y = t. (b) Use part (a) to show that the following problem, re- ferred to as the 3-Sum problem, can be solved in O(n2) time: 3-Sum Given an array A[1..n] of distinct positive integers, and...
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.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT