Étant donné un tableau binaire de taille n où n > 3 . Une valeur vraie (ou 1) dans le tableau signifie actif et fausse (ou 0) signifie inactif. Étant donné un nombre k, la tâche consiste à trouver le nombre de cellules actives et inactives après k jours. Après chaque jour, le statut de la ième cellule devient actif si les cellules gauche et droite ne sont pas identiques et inactif si les cellules gauche et droite sont identiques (les deux 0 ou les deux 1).
Puisqu'il n'y a pas de cellules avant les cellules les plus à gauche et après les cellules les plus à droite, la valeur des cellules avant les cellules les plus à gauche et après les cellules les plus à droite est toujours considérée comme 0 (ou inactive).
Exemples :
Input : cells[] = {1 0 1 1} k = 2 Output : Active cells = 3 Inactive cells = 1 After 1 day cells[] = {0 0 1 1} After 2 days cells[] = {0 1 1 1} Input : cells[] = {0 1 0 1 0 1 0 1} k = 3 Output: Active Cells = 2 Inactive Cells = 6 Explanation : After 1 day cells[] = {1 0 0 0 0 0 0 0} After 2 days cells[] = {0 1 0 0 0 0 0 0} After 3 days cells[] = {1 0 1 0 0 0 0 0} Input : cells[] = {0 1 1 1 0 1 1 0} k = 4 Output: Active Cells = 3 Inactive Cells = 5 La seule chose importante est de nous assurer que nous conservons une copie du tableau donné car nous avons besoin que les valeurs précédentes soient mises à jour pour le lendemain. Vous trouverez ci-dessous les étapes détaillées.
- Nous copions d’abord le tableau cell[] dans le tableau temp[] et apportons des modifications au tableau temp[] en fonction des conditions données.
- Dans la condition, il est donné que si les cellules gauche et droite immédiates de la ième cellule sont inactives ou actives le lendemain, je devient inactive, c'est-à-dire ; (cells[i-1] == 0 et Cells[i+1] == 0) ou (cells[i-1] == 1 et Cells[i+1] == 1) alors Cells[i] = 0, ces conditions peuvent être appliquées en utilisant XOR de Cells[i-1] et Cells[i+1].
- Pour la 0ème cellule d'index temp[0] = 0^cells[1] et pour la (n-1)ème cellule d'index temp[n-1] = 0^cells[n-2].
- Maintenant, pour les index 1 à n-2, effectuez l'opération suivante temp[i] = Cells[i-1] ^ Cells[i+1]
- Répétez le processus jusqu’à ce que k jours soient terminés.
Voici la mise en œuvre des étapes ci-dessus.
C++
// C++ program to count active and inactive cells after k // days #include
// Java program to count active and // inactive cells after k days class GFG { // cells[] - store current status // of cells n - Number of cells // temp[] - to perform intermediate operations // k - number of days // active - count of active cells after k days // inactive - count of active cells after k days static void activeAndInactive(boolean cells[] int n int k) { // copy cells[] array into temp [] array boolean temp[] = new boolean[n]; for (int i = 0; i < n; i++) temp[i] = cells[i]; // Iterate for k days while (k-- > 0) { // Finding next values for corner cells temp[0] = false ^ cells[1]; temp[n - 1] = false ^ cells[n - 2]; // Compute values of intermediate cells // If both cells active or inactive then // temp[i]=0 else temp[i] = 1. for (int i = 1; i <= n - 2; i++) temp[i] = cells[i - 1] ^ cells[i + 1]; // Copy temp[] to cells[] for next iteration for (int i = 0; i < n; i++) cells[i] = temp[i]; } // count active and inactive cells int active = 0 inactive = 0; for (int i = 0; i < n; i++) if (cells[i] == true) active++; else inactive++; System.out.print('Active Cells = ' + active + ' ' + 'Inactive Cells = ' + inactive); } // Driver code public static void main(String[] args) { boolean cells[] = {false true false true false true false true}; int k = 3; int n = cells.length; activeAndInactive(cells n k); } } // This code is contributed by Anant Agarwal.
# Python program to count # active and inactive cells after k # days # cells[] - store current # status of cells # n - Number of cells # temp[] - to perform # intermediate operations # k - number of days # active - count of active # cells after k days # inactive - count of active # cells after k days def activeAndInactive(cellsnk): # copy cells[] array into temp [] array temp=[] for i in range(n+1): temp.append(False) for i in range(n): temp[i] = cells[i] # Iterate for k days while (k >0): # Finding next values for corner cells temp[0] = False^cells[1] temp[n-1] = False^cells[n-2] # Compute values of intermediate cells # If both cells active or # inactive then temp[i]=0 # else temp[i] = 1. for i in range(1n-2+1): temp[i] = cells[i-1] ^ cells[i+1] # Copy temp[] to cells[] # for next iteration for i in range(n): cells[i] = temp[i] k-=1 # count active and inactive cells active = 0 inactive = 0; for i in range(n): if(cells[i] == True): active+=1 else: inactive+=1 print('Active Cells ='active' ' 'Inactive Cells =' inactive) # Driver code cells = [False True False True False True False True] k = 3 n =len(cells) activeAndInactive(cells n k) # This code is contributed # by Anant Agarwal.
// C# program to count active and // inactive cells after k days using System; class GFG { // cells[] - store current status // of cells n - Number of cells // temp[] - to perform intermediate // operations k - number of days // active - count of active cells // after k days inactive - count // of active cells after k days static void activeAndInactive(bool []cells int n int k) { // copy cells[] array into // temp [] array bool []temp = new bool[n]; for (int i = 0; i < n; i++) temp[i] = cells[i]; // Iterate for k days while (k-- > 0) { // Finding next values // for corner cells temp[0] = false ^ cells[1]; temp[n - 1] = false ^ cells[n - 2]; // Compute values of intermediate cells // If both cells active or inactive then // temp[i]=0 else temp[i] = 1. for (int i = 1; i <= n - 2; i++) temp[i] = cells[i - 1] ^ cells[i + 1]; // Copy temp[] to cells[] // for next iteration for (int i = 0; i < n; i++) cells[i] = temp[i]; } // count active and inactive cells int active = 0 inactive = 0; for (int i = 0; i < n; i++) if (cells[i] == true) active++; else inactive++; Console.Write('Active Cells = ' + active + ' ' + 'Inactive Cells = ' + inactive); } // Driver code public static void Main() { bool []cells = {false true false true false true false true}; int k = 3; int n = cells.Length; activeAndInactive(cells n k); } } // This code is contributed by Nitin Mittal.
// PHP program to count active // and inactive cells after k // days // cells[] - store current status // of cells n - Number of cells // temp[] - to perform intermediate // operations k - number of days // active - count of active cells // after k days inactive - count of // active cells after k days function activeAndInactive($cells $n $k) { // copy cells[] array into // temp [] array $temp = array(); for ($i = 0; $i < $n ; $i++) $temp[$i] = $cells[$i]; // Iterate for k days while ($k--) { // Finding next values // for corner cells $temp[0] = 0 ^ $cells[1]; $temp[$n - 1] = 0 ^ $cells[$n - 2]; // Compute values of // intermediate cells // If both cells active // or inactive then temp[i]=0 // else temp[i] = 1. for ($i = 1; $i <= $n - 2; $i++) $temp[$i] = $cells[$i - 1] ^ $cells[$i + 1]; // Copy temp[] to cells[] // for next iteration for ($i = 0; $i < $n; $i++) $cells[$i] = $temp[$i]; } // count active and // inactive cells $active = 0;$inactive = 0; for ($i = 0; $i < $n; $i++) ($cells[$i] == 1)? $active++ : $inactive++; echo 'Active Cells = ' $active ' Inactive Cells = ' $inactive; } // Driver Code $cells= array(0 1 0 1 0 1 0 1); $k = 3; $n = count($cells); activeAndInactive($cells $n $k); // This code is contributed by anuj_67. ?> <script> // javascript program to count active and // inactive cells after k days // cells - store current status // of cells n - Number of cells // temp - to perform intermediate operations // k - number of days // active - count of active cells after k days // inactive - count of active cells after k days function activeAndInactive(cells n k) { // copy cells array into temp array var temp = Array(n).fill(false); for (i = 0; i < n; i++) temp[i] = cells[i]; // Iterate for k days while (k-- > 0) { // Finding next values for corner cells temp[0] = false ^ cells[1]; temp[n - 1] = false ^ cells[n - 2]; // Compute values of intermediate cells // If both cells active or inactive then // temp[i]=0 else temp[i] = 1. for (i = 1; i <= n - 2; i++) temp[i] = cells[i - 1] ^ cells[i + 1]; // Copy temp to cells for next iteration for (i = 0; i < n; i++) cells[i] = temp[i]; } // count active and inactive cells var active = 0 inactive = 0; for (i = 0; i < n; i++) if (cells[i] == true) active++; else inactive++; document.write('Active Cells = ' + active + ' ' + 'Inactive Cells = ' + inactive); } // Driver code var cells = [ false true false true false true false true ]; var k = 3; var n = cells.length; activeAndInactive(cells n k); // This code is contributed by Rajput-Ji </script>
Sortir
Active Cells = 2 Inactive Cells = 6
Complexité temporelle : O(N*K) où N est la taille d'un tableau et K le nombre de jours.
Espace auxiliaire : O(N)
Cet article est révisé par l'équipe geeksforgeeks. Si vous avez une meilleure approche pour ce problème, partagez-la.