Givet en binær matrix af størrelse n hvor . En sand (eller 1) værdi i arrayet betyder aktiv og falsk (eller 0) betyder inaktiv. Givet et tal k er opgaven at finde antallet af aktive og inaktive celler efter k dage. Efter hver dag bliver status for i'te celle aktiv, hvis venstre og højre celler ikke er ens, og inaktive, hvis venstre og højre celle er ens (begge 0 eller begge 1).
Da der ikke er nogen celler før cellerne længst til venstre og efter cellerne længst til højre, betragtes værdicellerne før cellerne længst til venstre og efter cellerne længst til højre altid som 0 (eller inaktive).
Eksempler:
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 Det eneste vigtige er at sikre, at vi bevarer en kopi af et givet array, fordi vi har brug for tidligere værdier for at opdatere til næste dag. Nedenfor er detaljerede trin.
- Først kopierer vi cellerne[]-arrayet til temp[]-arrayet og foretager ændringer i temp[]-arrayet i henhold til den givne betingelse.
- I den betingelse er det givet, at hvis den umiddelbare venstre og højre celle i den i'te celle enten er inaktiv eller aktiv den næste dag, bliver jeg inaktiv, dvs. (celler[i-1] == 0 og celler[i+1] == 0) eller (celler[i-1] == 1 og celler[i+1] == 1) så kan celler[i] = 0 disse betingelser anvendes ved hjælp af XOR af celler[i-1] og celler[i+1].
- For 0'te indekscelle temp[0] = 0^celler[1] og for (n-1)'te indekscelle temp[n-1] = 0^celler[n-2].
- For indeks 1 til n-2 skal du udføre følgende operation temp[i] = celler[i-1] ^ celler[i+1]
- Gentag processen indtil k dage er afsluttet.
Følgende er implementeringen af ovenstående trin.
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>
Produktion
Active Cells = 2 Inactive Cells = 6
Tidskompleksitet: O(N*K) hvor N er størrelsen af en matrix og K er antallet af dage.
Hjælpeplads: O(N)
Denne artikel er gennemgået af team geeksforgeeks. Hvis du har en bedre tilgang til dette problem, så del venligst.