A file F holds the non-zero elements of two large n×n matrices, A and B.

The matrix entries are stored as triplets (i,j,value),

where value is the (i,j)th element of a matrix.

The file first stores the elements of A and then those of B. The matrix elements are stored in F in an arbitrary order.

In each matrix, only the elements {(i,i) : i = 1,...,n},

{(j,j + 1) : j = 1,...,n−1}, and

{(j + 1,j);j = 1,...,n−1}

are non-zero.

You are to add A and B and store the sum in C and then print A, B and C.

Due to limited memory, for storing all three matrices, you can use space to hold only up to 9n values (NOT triplets).

Is it possible to have an O(n) solution? If no, give reasons. If yes, provide a solution. Clearly explain the data structure and how you are going to store, retrieve, and add the elements.


Here only the elements (i,i) , (j,j+1) , (j+1,j) of the matrices A and B are non - zero.

So, we have to retrieve only the values of (i,i) , (j,j+1) , (j+1,j) of the matrices A and B from the file.

I want to know whether retrieving the values from file takes time or it can be done in constant time.

If it takes time then I think it is not possible to have an O(n) solution to the problem.

Please correct me if I am wrong.

If it takes constant time then please provide a algorithm to solve the problem in O(n) time.

  • 1
    $\begingroup$ Why do you think you need constant time file input? As long as you spend O(n) time in file access, you'll be fine. $\endgroup$
    – chi
    Commented Jun 18, 2018 at 10:12
  • $\begingroup$ @chi yes you are right but can it be done in O(n) time.I think it would take O(n2) time in file access. $\endgroup$ Commented Jun 18, 2018 at 10:58
  • $\begingroup$ Only the non-zero elements are stored in the file. So there are at most 3n triplets to read from the file. It seems you can read the three diagonals in three arrays using 3n memory and O(n) time. $\endgroup$
    – chi
    Commented Jun 18, 2018 at 11:44
  • $\begingroup$ Where did you encounter this problem? Can you credit the original source? $\endgroup$
    – D.W.
    Commented Jun 18, 2018 at 17:48
  • $\begingroup$ Cross-posted: stackoverflow.com/q/50870505/781723, cs.stackexchange.com/q/93195/755. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$
    – D.W.
    Commented Jun 18, 2018 at 17:49


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.