Programming & Computer Science Answers

You are given some coins. You have to take some coins from the given coins such that the sum of the coins

you took have a value strictly larger than the sum of the rest of the coins. However, you have to take

minimum number of coins while satisfying this condition

Input

In the first line, you are given n (n<=100), the number of integer numbers. In the next line, you will be given n integers, separated by spaces.

Output

Output one number, the minimum number of coins you need to take to have a larger sum than the sum of the

coins you did not take.

Input Output

2 2

3 3

3 2

2 1 2

6 2

4 2 1 2 1 1

In the first sample you will have to take 2 coins. If you take 1 coin, you get sum 3, 3. If you take 0 coins, you get

sums 0, 6. Those variants do not satisfy you as your sum should be strictly more than the other sum.

In the second sample one coin isn't enough for you, too. You can pick coins with values 1, 2 or 2, 2. In any case,

the minimum number of coins equals 2.

.

Add to the time class hat has separate in member data for hours, minutes, and Seconds the ability to subtract two time values using the overloaded (-) operator, and to multiply a time value by a number of type float, using the overloaded (*) operator.

 Assume that the coin information is given to you in the form of an ‘n’ element array A. A[i] is a number between 1 and n and A[i] = j means that the j’th smallest pancake is in position i from the top; in other words A[1] is the size of the top most coin (relative to the others) and

A[n] is the size of the bottommost coin. 

operation(A, n) should be assumed to be O(1) can be used directly in pseudo code, it flips first n coins.

Consider a pile of coins. You have given ‘n’ coins of different sizes and you want to sort the pile so that smaller coins are on the top of larger ones. The only “operation” you are allowed to perform is- take top ‘k’ coins together, and place them back to the pile upside down

Rahul lives in City A and would like to travel to City B for work. There is a shuttle service for people in these cities which has a fixed schedule. The schedule for City A is a list of boarding times(at City A) and departure times(from City A) for each bus.

Note: No one is allowed to board a shuttle after the boarding time.

He arrives at time t and sometimes has to wait at the station. You are given a list of arrival times for n days.

Question 1.

Mickeymouse loves numbers in the range [m1, m2] (m1 and m2 included). Minnie decides to gift Mickey an array of numbers for his birthday. Mickey wants to find the number of pairs of indices [l, r] for which the sum of all the  elements in the range [l, r] lies between m1 and m2.   

1. Come up with an algorithm with a worst case complexity of O(N2).   (5 marks) 
2. Now improvise this algorithm, assuming all numbers are positive integers.    (7 marks)
3. What if the numbers could be negative as well? Can you think of an O(nlogn) solution in this case? (Hint: use sorting)  (10 marks)

Sample case: 

Array = [-2, 5, -1]

M1 = -2

M2 = 2

Output: 3 

[[0, 0], [2, 2], [0, 2]] are the three pairs of [l, r] that satisfy the condition. So, that is why, the output is 3.  

Notes: Recurrence relation not needed in first two parts. But do explain the reason for the resulting time complexity in words. 

With aid of a diagram, give a brief explanation on the type of busses available on 

modern computer systems and the purpose of the North Bridge and South Bridge. 

Your diagram should clearly show where the bridges are and what connects them