in Algorithms edited by
642 views
2 votes
2 votes
The Income-Tax Department had prepared a list D of names of defaulters on March $31$. However, the government extended the deadline to pay taxes till April $15$.
The IT department has now received two additional lists of names: a list B of names of people who have paid their taxes between April $1$ and April $15$ at a bank, and a list O of names of people have paid their taxes during this period online. Some people have paid part of their taxes at a bank and part online, so there may be names that appear in both B and O.
From the lists D, B and O, the IT department wants to prepare a revised list of defaulters. The names in the original list D are sorted in alphabetical order while the names in B and O are listed according to the date on which they paid their taxes. Fortunately, no two people have the same name.
Describe an efficient algorithm to compute the revised list of defaulters. Assume that the size of D, B and O is n, m and k respectively and that $n > m > k$. Describe the running time of your algorithm in terms of these parameters.
in Algorithms edited by
642 views

2 Comments

I can't think of an "efficient" algorithm. Brute force method will take n (m +k) time.
0
0
how u calculating time?
0
0

1 Answer

0 votes
0 votes
STEP 1 :- Start

STEP 2 :- Merge the lists B and O into a new list (B&O) such that the names in the new list (B&O) are distinct and are sorted in alphabetical order. This would take O(m+k) time.

STEP 3:- Take two pointer variables i and j such that i points to the names in the list D and j points to the names in the list (B&O).

STEP 4:- If the name pointed by i is same as the name pointed by j then delete the name pointed by i and increment both the pointers i and j.

STEP 5:- Otherwise increment the pointer i.

STEP 6:- Repeat the Steps 4 & 5 till the end of the list (B&O). This process of deleting names from the list D would take O(n) time.

STEP 7:- STOP

Time Complexity O(n + m + k).

3 Comments

If I solve the problem above in this way:

 

take each name one by one first from B and then from O,

For each name taken from either of the list apply binary search in the list D (as it is given that D is sorted in alphabetical order).

Total time would be : (n+k)logm.

Please help and comment if I am thinking in wrong direction
0
0
For Step 2, directly we can't apply merge sort. Because the elements in list B and list C are not in sorted order.
2
2
yes we have to sorte the list B and O first.
0
0

Related questions