Tenemos una array cuadrada cuyo tamaño se expande continuamente por un factor de 2. Dada una secuencia presente en la array en la posición (i, j) en cualquier momento, necesitamos devolver la secuencia presente en la posición (i, (j + N -1)%N) donde N es el tamaño de la array.
Cuando decimos que la array se está expandiendo, la array expandida se forma multiplicando cada elemento de la array original de 2 x 2 con la propia array N x N actual. La array expandida tendrá unas dimensiones de 2N x 2N.
For Instance, consider below 2x2 matrix,
[a b]
Expanding it will result in a 4x4 matrix as follows:
ax[a b] bx[a b] [aa ab ba bb]
[ac ad bc bd]
--> [ca cb da db]
cx[a b] dx[a b] [cc cd dc dd]
Expanding it again results in an 8x8 matrix as follows, and so on.
ax[aa ab ba bb] bx[aa ab ba bb] [aaa aab aba abb baa bab bba bbb]
[ac ad bc bd] [ac ad bc bd] [aac aad abc abd bac bad bbc bbd]
[ca cb da db] [ca cb da db] [aca acb ada adb bca bcb bda bdb]
[cc cd dc dd] [cc cd dc dd] [acc acd adc add bcc bcd bdc bdd]
--> [caa cab cba cbb daa dab dba dbb]
cx[aa ab ba bb] dx[aa ab ba bb] [cac cad cbc cbd dac dad dbc dbd]
[ac ad bc bd] [ac ad bc bd] [cca ccb cda cdb dca dcb dda ddb]
[ca cb da db] [ca cb da db] [ccc ccd cdc cdd dcc dcd ddc ddd]
[cc cd dc dd] [cc cd dc dd]
Básicamente, para una secuencia dada, necesitamos encontrar la secuencia que le queda. Se puede suponer que la array es circular, es decir, la secuencia presente en la posición (i, 0) debe devolver la secuencia presente en la posición (i, N-1)
Ejemplos:
Input: str = dda Output: dcb Input: str = cca Output: ddb Input: str = aacbddc Output: aacbdcd
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Si analizamos cuidadosamente, podemos ver un patrón aquí.
Algoritmo:
Comenzamos a escanear la string desde la posición más a la derecha y para cada carácter hacemos lo siguiente:
- Si el carácter actual es ‘b’ o ‘d’, cambie a ‘a’ o ‘c’ respectivamente y devuelva la string.
- Si el carácter actual es ‘a’ o ‘c’, cámbielo a ‘b’ o ‘d’ respectivamente y pase al siguiente carácter a la izquierda. Repita el paso 1 para el siguiente carácter de la izquierda.
Implementación:
C++
// C++ Program to return previous element in an expanding
// matrix.
#include <bits/stdc++.h>
using namespace std;
// Returns left of str in an expanding matrix of
// a, b, c, and d.
string findLeft(string str)
{
int n = str.length();
// Start from rightmost position
while (n--)
{
// If the current character is ‘b’ or ‘d’,
// change to ‘a’ or ‘c’ respectively and
// break the loop
if (str[n] == 'd')
{
str[n] = 'c';
break;
}
if (str[n] == 'b')
{
str[n] = 'a';
break;
}
// If the current character is ‘a’ or ‘c’,
// change it to ‘b’ or ‘d’ respectively
if (str[n] == 'a')
str[n] = 'b';
else if (str[n] == 'c')
str[n] = 'd';
}
return str;
}
// driver program to test above method
int main()
{
string str = "aacbddc";
cout << "Left of " << str << " is "
<< findLeft(str);
return 0;
}
Java
// Java program to return previous element
// in an expanding matrix
import java.io.*;
class GFG
{
// Returns left of str in an expanding matrix
// of a, b, c and d.
static StringBuilder findLeft(StringBuilder str)
{
int n = str.length();
// Start from rightmost position
while (n > 0)
{
n--;
// If the current character is b or d,
// change to a or c respectively and
// break the loop
if (str.charAt(n) == 'd')
{
str.setCharAt(n,'c');
break;
}
if (str.charAt(n) == 'b')
{
str.setCharAt(n,'a');
break;
}
// If the current character is a or c,
// change it to b or d respectively
if (str.charAt(n) == 'a')
str.setCharAt(n,'b');
else if (str.charAt(n) == 'c')
str.setCharAt(n,'d');
}
return str;
}
// driver program to test above method
public static void main (String[] args)
{
StringBuilder str = new StringBuilder("aacbddc");
System.out.print("Left of " + str + " is " +
findLeft(str));
}
}
// This code is contributed by Prakriti Gupta
Python3
# Python3 Program to return previous element
# in an expanding matrix.
# Returns left of str in an
# expanding matrix of a, b, c, and d.
def findLeft(str):
n = len(str) - 1;
# Start from rightmost position
while (n > 0):
# If the current character is ‘b’ or ‘d’,
# change to ‘a’ or ‘c’ respectively and
# break the loop
if (str[n] == 'd'):
str = str[0:n] + 'c' + str[n + 1:];
break;
if (str[n] == 'b'):
str = str[0:n] + 'a' + str[n + 1:];
break;
# If the current character is ‘a’ or ‘c’,
# change it to ‘b’ or ‘d’ respectively
if (str[n] == 'a'):
str = str[0:n] + 'b' + str[n + 1:];
else if (str[n] == 'c'):
str = str[0:n] + 'd' + str[n + 1:];
n-=1;
return str;
# Driver Code
if __name__ == '__main__':
str = "aacbddc";
print("Left of", str, "is", findLeft(str));
# This code is contributed by PrinciRaj1992
C#
using System;
using System.Text;
// C# program to return previous element
// in an expanding matrix
public class GFG
{
// Returns left of str in an expanding matrix
// of a, b, c and d.
public static StringBuilder findLeft(StringBuilder str)
{
int n = str.Length;
// Start from rightmost position
while (n > 0)
{
n--;
// If the current character is b or d,
// change to a or c respectively and
// break the loop
if (str[n] == 'd')
{
str[n] = 'c';
break;
}
if (str[n] == 'b')
{
str[n] = 'a';
break;
}
// If the current character is a or c,
// change it to b or d respectively
if (str[n] == 'a')
{
str[n] = 'b';
}
else if (str[n] == 'c')
{
str[n] = 'd';
}
}
return str;
}
// driver program to test above method
public static void Main(string[] args)
{
StringBuilder str = new StringBuilder("aacbddc");
Console.Write("Left of " + str + " is " + findLeft(str));
}
}
// This code is contributed by Shrikant13
PHP
<?php
// PHP program to return previous element in an expanding
// matrix.
// Returns left of str in an expanding matrix of
// a, b, c and d.
function findLeft($str)
{
$n = strlen($str);
// Start from rightmost position
while ($n--)
{
// If the current character is ‘b’ or ‘d’,
// change to ‘a’ or ‘c’ respectively and
// break the loop
if ($str[$n] == 'd')
{
$str[$n] = 'c';
break;
}
if ($str[$n] == 'b')
{
$str[$n] = 'a';
break;
}
// If the current character is ‘a’ or ‘c’,
// change it to ‘b’ or ‘d’ respectively
if ($str[$n] == 'a')
$str[$n] = 'b';
else if ($str[$n] == 'c')
$str[$n] = 'd';
}
return $str;
}
// Driver Code
$str = "aacbddc";
echo "Left of " . $str . " is "
. findLeft($str);
return 0;
?>
Javascript
<script>
// Javascript program to return previous element
// in an expanding matrix
String.prototype.replaceAt = function(index, replacement)
{
return this.substr(0, index) + replacement + this.substr(index + replacement.length);
}
// Returns left of str in an expanding matrix
// of a, b, c and d.
function findLeft(str)
{
let n = str.length;
// Start from rightmost position
while (n > 0)
{
n--;
// If the current character is b or d,
// change to a or c respectively and
// break the loop
if (str[n] == 'd')
{
str = str.replaceAt(n,'c');
break;
}
if (str[n] == 'b')
{
str = str.replaceAt(n, 'a');
break;
}
// If the current character is a or c,
// change it to b or d respectively
if (str[n] == 'a')
str = str.replaceAt(n, 'b');
else if (str[n] == 'c')
str = str.replaceAt(n, 'd');
}
return str;
}
// driver program to test above method
let str = "aacbddc";
document.write("Left of " + str + " is " +
findLeft(str));
// This code is contributed by rag2127.
</script>
Producción
Left of aacbddc is aacbdcd
Complejidad temporal: O(n).
Espacio Auxiliar: O(1).
Este artículo es una contribución de Aarti_Rathi y Aditya Goel . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA