Only the non-zero elements are stored in the file. So, there are only (6n -4) triplets.
So, accessing any triplet would take O(n) time.
Since it is given in the question that the main memory can store 9n values.
So, we construct 9 arrays.
i) A1 of size n-1
where A1 will store first n-1 values of the triplets (j,j+1,value)
A1 [j] = value of the triplet (j,j+1,value).
ii) B1 of size n-1.
Where B1 will store the next n-1 values of the triplets (j,j+1,value)
B1 [j] = value of the triplet (j,j+1,value)
iii) C1 of size n-1
where C1 [j] = A1 [j] + B1 [j]
iv) A2 of size n
where A2 will store first n values of the triplets (j,j,value)
A2 [j] = value of the triplet (j,j,value)
v) B2 of size n
where B2 will store next n values of the triplets (j,j,value)
B2 [j] = value of the triplet (j,j,value)
vi) C2 of size n
where C2 [j] = A2 [j] + B2 [j]
vii) A3 of size n-1
where A3 will store first n-1 values of the triplets (j+1,j,value)
A3 [j] = value of the triplet (j+1,j,value)
viii) B3 of size n
where B3 will store next n values of the triplets (j+1,j,value)
B3 [j] = value of the triplet (j+1,j,value)
ix) C3 of size n
where C3 [j] = A3 [j] + B3 [j]
Now, we are told to print the matrices A and B. This can be done by scanning through the file F and print the values of first (3n-2) triplets in the corresponding places in the matrix A and print the values of the next (3n-2) triplets in the corresponding places in the matrix B.
Rest elements of A and B are printed 0.
And for printing C we know,
(j,j+1)th element of C = C1 [j]
(j,j)th element of C = C2 [j]
(j+1,j)th element of C = C3[j]
And rest of the elements of C are printed as 0..
So, the data structure used in my solution is array.
and the time complexity is O(n).