In an extended matrix, return the previous element in C++

Discuss a problem based on the extended matrix. An extended matrix is ​​a matrix whose size increases by some factor.

Here we have a character matrix whose size is expanded by a multiple of 2, that is, if the size of the original matrix is ​​N * N, then the size of the expanded matrix becomes 2N * 2N. We are given a sequence of characters located at (i, j) and we need to return the sequence of characters located at (i, (j - N - 1)%N).

Let us understand by visualizing some initial expansion matrices.

Given Matrix -> [ a, b ] [ c, d ], 2 X 2 matrix
Multiplying with { a, b, c, d }
A X [ a, b ]
B X [ a, b ]
C X [ a, b ]
D X [ a, b ]
[ c, d ] [ c, d ] [ c, d ] [ c, d ]

Expanded Matrix -> [ aa, ab, ba, bb ]
[ ac, ad, bc, bd ]
[ ca, cb, da, db ]
[ cc, cd, dc, dd ], 4X4 matrix
To expand again, multiply it by { a, b, c, d } and a matrix of size 8X8 will be formed.

Expanded Matrix - > [ aaa, aab, aba, abb, baa, bab, bba, bbb ]
[ aac, aad, abc, abd, bac, bad, bbc, bbd ]
[ aca, acb, ada, adb, bca, bcb, bda, bdb ]
[ acc, acd, adc, add, bcc, bcd, bdc, bdd ]
[ caa, cab, cba, cbb, daa, dab, dba, dbb ]
[ cac, cad, cbc, cbd, dac, dad, dbc, dbd ]
[ cca, ccb, cda, cdb, dca, dcb, dda, ddb ]
[ ccc, ccd, cdc, cdd, dcc, dcd, ddc, ddd ]

These are two initial expansion matrices; assuming we get a character sequence "bcc", then we need to return the sequence just left, which is "add". Also, assume that the matrix is ​​cyclic, i.e. if the given sequence is at (i, 0), then return the sequence at (i, N-1)

Input: abb
Output: aba
Explanation: The sequence just left to abb is aba in the 8X8 matrix.

Input: aadc
Output: aacd

Input: abbcd
Output: abbcc

Methods to find the solution

Thinking about the problem first, the only solution that comes to mind is to find the extended matrix that contains the given sequence but doesn't look very complex. We need to form the matrix first and then search for the sequence.

Efficient Method

After looking at some initially expanded matrices, we discovered a pattern through which we could see the previous element. That is,

• traverses the character sequence starting from the last index.

• If the index element is 'b' or 'd', then change it to 'a' or 'c' and stop traversing the array.

• If the index element is 'a' or 'c', ' change it to 'b' or 'd' and move to the next index and check it.

Example

C code above method

#include <bits/stdc++.h>
using namespace std;
int main (){
   string seq = "abbcd";
   int n = seq.length ();
   // traverse through the string from last.
   for (int i = n; i >= 0; i--){
      // if the element is b or d, change them and stop traversing.
      if (seq[i] == &#39;b&#39;){
      seq[i] = &#39;a&#39;;
      break;
   }
   if (seq[i] == &#39;d&#39;){
      seq[i] = &#39;c&#39;;
      break;
   }
   // if an element is b or d, change them and move to the next element.
   if (seq[i] == &#39;a&#39;)
      seq[i] = &#39;b&#39;;
   else if (seq[i] == &#39;c&#39;)
      seq[i] = &#39;d&#39;;
   }
   cout << "The Previous sequence is: " << seq;
   return 0;
}

Output

The previous sequence is: abbcc

Conclusion

In this article, we discussed extended character matrices and how they are formed. We also discussed finding the previous element in an extended matrix. We solved this problem by understanding the patterns created by the extended character matrix.

We also discussed C code to solve this problem, which we can write in any programming language like C, Java, Python, etc. We hope you find this tutorial helpful.

The above is the detailed content of In an extended matrix, return the previous element in C++. For more information, please follow other related articles on the PHP Chinese website!