Question
(i) Design an efficient algorithm (pseudocode or a succinct verbal description) that checks whether an array of size n has a pair of numbers whose product is M.
(ii) What is the worst-case running time for your solution? Explain.
(iii) Using a loop invariant, prove that your algorithm is correct.
*Tip: Given {5, 2, 7, 4, 6} and M = 28 your solution should return "True" (because 7x4=28).
------ Quadratic time algorithms are not efficient solutions.
Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references.
Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.

Pseudocode:

1. Create an empty HashMap
2. Traverse array elments and do following for every element arr[i].
â–ª If arr[i] is 0 and M is also 0, return true, else ignore arr[i].
â–ª If M % arr[i] is 0 and M/arr[i] exists in table, return true.
â–ª Insert arr[i] into the hash table.
3. Return false

Detailed Explanation:

1. You create a function which takes the array and the product M as input.
2. You iterate through the elements of the array.
For each element,
if the element is 0 and the product you are looking for is also 0 then return TRUE.
else, continue;
This is only a preview of the solution.
Please use the purchase button to see the entire solution.
By purchasing this solution you'll be able to access the following files:
Solution.docx
Purchase Solution
$18.00
Google Pay
Amazon
Paypal
Mastercard
Visacard
Discover
Amex
View Available Computer Science Tutors 645 tutors matched
ionut
Ionut
(ionut)
Master of Computer Science
Hi! MSc Applied Informatics & Computer Science Engineer. Practical experience in many CS & IT branches.Research work & homework
5/5 (6,808+ sessions)
1 hour avg response
$15-$50 hourly rate
Pranay
(math1983)
Doctor of Philosophy (PhD)
Ph.D. in mathematics and working as an Assistant Professor in University. I can provide help in mathematics, statistics and allied areas.
4.6/5 (6,702+ sessions)
1 hour avg response
$40-$50 hourly rate
Leo
(Leo)
Doctor of Philosophy (PhD)
Hi! I have been a professor in New York and taught in a math department and in an applied math department.
4.9/5 (6,469+ sessions)
2 hours avg response

Similar Homework Solutions