Suppose you are given a list of n integers, each of size at most 100 n . How man

Question

Suppose you are given a list of n integers, each of size at most 100n. How many operations would it take you to do the following tasks (in answering these questions, we are interested primarily in whether it will take log n, n1/2, n, n2, n3, 2n, … steps. In other words, ignore multiplicative constants.):

a. Determine if the number 2n+7 is in the list.

b. Determine if there are two numbers in the list whose sum is 2n+7.

c. Determine if there are two numbers in the list whose product is 2n+7 (This one is more subtle than it might appear! It may be to your advantage to sort the integers in the list).

d. Determine if there is a number i for which all the numbers in the list are between i and i+2n+7.

e. Determine the longest sequence of consecutive integers belonging to the list.

f. Determine the number of primes in the list.

g. Determine whether there are three integers x, y and z from the list so that x+y=z.

h. Determine whether there are three integers x, y and z from the list so that x2+y2=z2.

i. Determine whether there are three integers x, y and z from the list so that xy=z.

j. Determine whether there are three integers x, y and z from the list so that xy=z.

k. Determine whether there are two integers x and y from the list so that xy is a prime.

l. Determine the longest arithmetic progression in the list (a sequence (a1, a2,…,at) is an arithmetic progression when there is a constant d 0 so that ai+1=ai+d, for each i=1,2,…,t1).

m. Determine the number of distinct sums that can be formed from members of the list (arbitrarily many integers from the list are allowed to be terms in the sum).

n. Determine the number of distinct products that can be formed from members of the list (arbitrarily many integers from the list are allowed to be factors in the product).

o. Determine for which integers m, the list contains at least 10% of the integers from {1, 2,…, m}.

Explanation / Answer

ANSWER:

a) Yes, it would take n steps, if the list is NOT sorted. If the list is sorted then it would take only log(n) step by using binary search.

b)          There is better solution and easy to implement: first sort the list (take n*log(n) steps), then iterate i from 0   to length(list)-1, perform binary search for number (2n + 7 - list[i]) in n-i-1 numbers on the right of list[i]. Iterate takes n steps, binary search takes log(n) steps, so overall you'll get n*log(n) steps. Plus n*log(n) steps from sorting the   list before you'll get 2*n*log(n) ~ n*log(n) steps, which is significantly faster than n^2

c)     The same as b) n*log(n), but binary search for number (2n + 7) / list[i] instead.

d)        Find minimum value in the list, which takes n steps, find maximum value in the list, which also takes n steps. If (max - min) > 2n + 7 then there is no i. If (max - min) <= 2n + 7 then certainly i = min will satisfy the condition. So you just need to find max and min, which takes n steps (again, if the list is not sorted, but if it is sorted then it would take only 2 steps ~ 1 step if you ignore multiplicative constant)

                                  (1 < log(n) << n < n log(n) << n^2 steps)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.