Notice difference with respect to question --> https://gateoverflow.in/1997/gate2014-2-38

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+17 votes

The minimum number of record movements required to merge five files A (with $10$ records), B (with $20$ records), C (with $15$ records), D (with $5$ records) and E (with $25$ records) is:

- $165$
- $90$
- $75$
- $65$

+23 votes

Best answer

Arrange files in increasing order of records:

$\overset{\boxed5}{\text{D}}\quad \overset{\boxed{10}}{\text{A}}\quad\overset{\boxed{15}}{\text{C}}\quad\overset{\boxed{20}}{\text{B}}\quad\overset{\boxed{25}}{\text{E}}$

$\qquad\qquad\qquad\qquad\color{blue}{75}$

$\qquad\qquad\quad\color{blue}{30}\qquad\qquad\qquad\color{blue}{45}$

$\qquad\quad\color{blue}{15}\qquad\overset{\boxed{\text{C}}}{15}\qquad\qquad\overset{\boxed{\text{B}}}{20}\qquad\overset{\boxed{\text{E}}}{25}$

$\quad\overset{\boxed{\text{D}}}{5}\qquad\overset{\boxed{\text{A}}} {10}$

No. of movements $=15+30+45+75=165.$

$\overset{\boxed5}{\text{D}}\quad \overset{\boxed{10}}{\text{A}}\quad\overset{\boxed{15}}{\text{C}}\quad\overset{\boxed{20}}{\text{B}}\quad\overset{\boxed{25}}{\text{E}}$

$\qquad\qquad\qquad\qquad\color{blue}{75}$

$\qquad\qquad\quad\color{blue}{30}\qquad\qquad\qquad\color{blue}{45}$

$\qquad\quad\color{blue}{15}\qquad\overset{\boxed{\text{C}}}{15}\qquad\qquad\overset{\boxed{\text{B}}}{20}\qquad\overset{\boxed{\text{E}}}{25}$

$\quad\overset{\boxed{\text{D}}}{5}\qquad\overset{\boxed{\text{A}}} {10}$

No. of movements $=15+30+45+75=165.$

+1

Hi Pooja

I am not able to follow how did you get 45 ?

Could u please explain it for me.

Thanks in advance.

# Update:Understood.! First three files u merged and then u merged last two files and then clubbed u merged the two!

I am not able to follow how did you get 45 ?

Could u please explain it for me.

Thanks in advance.

# Update:Understood.! First three files u merged and then u merged last two files and then clubbed u merged the two!

+1

"This is **different** from another greedy problem in which **we simply merge the files one into another in after arranging them in ascending order**."

In the above solved question, we have used to "MERGE" procedure from merge sort which takes one element of each array compare them and put them in the final or output array.

- Movement of record is analogous to the movement of elements of arrays which we merge and no. of element get moved in MERGE producer are "all" i.e m+n.
- Comparisons would be just m+n-1 as last element remaining does not need any comparison to put it into the output array.

more:-https://gateoverflow.in/1997/gate2014-2-38?show=7132#c7132

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,716 questions

46,751 answers

140,564 comments

58,409 users