Given a collection of n nuts, and a collection of n bolts, each arranged in an increasing order of size, give an O(n) time algorithm to check if there is a nut and a bolt that have the same size. You can assume that the sizes of the nuts and bolts are stored in the arrays NUTS[1::n] and BOLTS[1::n], respectively, where NUTS[1] < < NUTS[n] and BOLTS[1] < < BOLTS[n]. Note that you only need to report whether or not a match exists; you do not need to report all matches.
1 answer
Question:
Given a collection of n nuts, and a collection of n bolts, each arranged in an increasing order of size, give an O(n) time algorithm to check if there is a nut and a bolt that have the same size. You can assume that the sizes of the nuts and bolts are stored in the arrays NUTS[1::n] and BOLTS[1::n], respectively, where NUTS[1] < < NUTS[n] and BOLTS[1] < < BOLTS[n]. Note that you only need to report whether or not a match exists; you do not need to report all matches.
Answers
Answer:See explaination for the program codeExplanation:Keep two iterators, i (for nuts array) and j (for bolts array).while(i < n and j < n) {if nuts[i] == bolts[j] {We have a case where sizes match, output/return}else if nuts[i] < bolts[j] {this means that size of nut is smaller than that of bolt and we should go to the next bigger nut, i.e., i+=1}else {this means that size of bolt is smaller than that of nut and we should go to the next bigger bolt, i.e., j+=1}}Since we go to each index in both the array only once, the algorithm take O(n) time.
Similar Solved Questions
1 answer
In what sense is the earth a closed system? A) Earth’s atmosphere prevents the transfer of energy or matter between Earth and space. B) Earth’s atmosphere prevents the transfer of matter, but allows the transfer of energy between Earth and space. C) Earth’s atmosphere absorbs all of the Sun’s energy, but allows only a part of it to reach the surface of Earth. D) Earth’s atmosphere traps all of the Sun’s energy, thereby providing all living organisms the energy required to survive.
In what sense is the earth a closed system?
A) Earth’s atmosphere prevents the transfer of energy or matter between Earth and space.
B) Earth’s atmosphere prevents the transfer of matter, but allows the transfer of energy between Earth and space.
C) Earth’s atmosphere absorbs all of the Sun�...
1 answer
How was the Abbasids’ treatment of non-Muslims similar to that of the Umayyads’? How was it different?
How was the Abbasids’ treatment of non-Muslims similar to that of the Umayyads’? How was it different?...
1 answer
Choose a problem (and solutions) described in the text. Explain what the problem is and why it matters, using examples, facts, and details from the text. If possible, describe any solutions proposed in the text. newsela article Human connection bolsters immune system; that's why it's important to be kind
Choose a problem (and solutions) described in the text. Explain what the problem is and why it matters, using examples, facts, and details from the text. If possible, describe any solutions proposed in the text.
newsela article
Human connection bolsters immune system; that's why it's important to b...
1 answer
Can species be considered natural resources?
Can species be considered natural resources?...
1 answer
Deluxe suites hotels incluedes the following selected accounts in its genarel ledger at December 31.2016: Notes Payable $200,000 Accounts Payable $33,000 Bonds Payable 450,000 Discounts on Bonds Payable 13,500 Interest Payable (due next year) 1,000 Salaries Payable 2,600 Estimated Warranty Payable 1,300 Sales Tax Payable 400 Required: Prepare the liabilities section of Luxury Suites' balance sheet at December 31.2016.
Deluxe suites hotels incluedes the following selected accounts in its genarel ledger at December 31.2016:
Notes Payable $200,000 Accounts Payable $33,000
Bonds Payable 450,000 Discounts on Bonds Payable 13,500
Interest Payable
(due next year) 1,000 Salaries Payable 2,600
Estimated Warranty
Payable...
1 answer
Meteorology has to do with weather and storms and such. Sometimes tsunamis can completely wipe out an entire part of an island, or a tornado can cause issues with large landforms. Weather is one of the main ways things have changed over the milleniums, and will still change it in the future.
Meteorology has to do with weather and storms and such. Sometimes tsunamis can completely wipe out an entire part of an island, or a tornado can cause issues with large landforms. Weather is one of the main ways things have changed over the milleniums, and will still change it in the future....
1 answer
Which of the following samples of gas would have a new volume of 3.00 liters if the pressure is decreased from 3.00 atm to 1.00 atm at constant temperature?
Which of the following samples of gas would have a new volume of 3.00 liters if the pressure is decreased from 3.00 atm to 1.00 atm at constant temperature?...
1 answer
The British National Debt in 1763 was caused by the continual presence of the British military in the American colonies, as well as, the French and Indian War. true or false
The British National Debt in 1763 was caused by the continual presence of the British military in the American colonies, as well as, the French and Indian War. true or false...
1 answer
1. You are analyzing a compound in the laboratory. You find that it is made up of carbon, hydrogen oxygen in a ratio of two hydrogen atoms for each carbon atom. How will you classify the compoun A. lipid B. protein C. carbohydrate D. nucleic acid 2. Fats, oils and cholesterol are all types of what? A. cell membranes B. hormones C. lipids D. fatty acids • A sugar, a phosphate group, and a nitrogen base form the building blocks of which organic compound? A. carbohydrates B. lipids C. nucleic acids
1. You are analyzing a compound in the laboratory. You find that it is made up of carbon, hydrogen
oxygen in a ratio of two hydrogen atoms for each carbon atom. How will you classify the compoun
A. lipid
B. protein
C. carbohydrate
D. nucleic acid
2. Fats, oils and cholesterol are all types of what?
...
2 answers
Which version of softball is most similar to baseball? A Pony league B Slow pitch C Fast pitch D Senior League
Which version of softball is most similar to baseball?
A Pony league
B Slow pitch
C Fast pitch
D Senior League...
1 answer
20 Which of the following is an unbalanced equation?* (1 Point) a. CaCO3 --> CaO + CO2 O b. 2PbO 2 + 2H 2 -->2Pb +2H2O O c. 2Na+ 2H 2 O-->2NASH + H 2 d. CS 2 + 20 2 --> CO 2 + 250 2
20
Which of the following is an unbalanced equation?*
(1 Point)
a. CaCO3 --> CaO + CO2
O b. 2PbO 2 + 2H 2 -->2Pb +2H2O
O c. 2Na+ 2H 2 O-->2NASH + H 2
d. CS 2 + 20 2 --> CO 2 + 250 2...
1 answer
What did you know for sure after one test? two test? three test?
what did you know for sure after one test? two test? three test?...
1 answer
Help me with this pls I will mark you as brain
Help me with this pls I will mark you as brain...
1 answer
Assume your organization has the following inventory changes during the year: Beginning Inventory 15 units Valued at $10,000 each February purchases 13 units at $11,500 each June purchases 20 units at $12,000 each Total units used 42 Calculate the value of the ending inventory and the value of the inventory used (the inventory expense) for the year, using both the FIFO and the LIFO method of cost-flow.
Assume your organization has the following inventory changes during the year:
Beginning Inventory 15 units
Valued at $10,000 each
February purchases 13 units at $11,500 each
June purchases 20 units at $12,000 each
Total units used 42
Calculate the value of the ending inventory and the value of...
1 answer
What are the predominant crops farmed in the Great Plains? A. lima beans, kidney beans and pinto beans B. avocados, tomatoes and strawberries C. corn, wheat and soybeans
What are the predominant crops
farmed in the Great Plains?
A. lima beans, kidney beans and pinto beans
B. avocados, tomatoes and strawberries
C. corn, wheat and soybeans...
1 answer
A baker cut a pie in thirds. He cut each third into 4 equal pieces and each piece into 2 equal slices. He sold 14 slices. What fraction of the pie did the baker sell? The baker sold of the pie.
A baker cut a pie in thirds. He cut each third into 4 equal pieces and each piece into 2 equal slices. He sold
14 slices.
What fraction of the pie did the baker sell?
The baker sold
of the pie....
1 answer
10 POINTS!!! An airplane takes four hours to travel a distance of 2800 miles with the wind. The return trip takes 5 hours against the wind. Find the speed of the plane in still air and the speed of the wind The speed of the plane is__ mph. And the speed of the wind is__ mph.
10 POINTS!!!
An airplane takes four hours to travel a distance of 2800 miles with the wind. The return trip takes 5 hours against the wind. Find the speed of the plane in still air and the speed of the wind
The speed of the plane is__ mph.
And the speed of the wind is__ mph....
1 answer
Brown’s plan was to instigate a major slave __________ in the South.
Brown’s plan was to instigate a major slave __________ in the South....