Aktiva och inaktiva celler efter k dagar
Givet en binär matris med storlek n där n > 3 . Ett sant (eller 1) värde i matrisen betyder aktivt och falskt (eller 0) betyder inaktivt. Givet ett nummer k är uppgiften att hitta antalet aktiva och inaktiva celler efter k dagar. Efter varje dag blir status för i:te cellen aktiv om vänster och höger cell inte är samma och inaktiv om vänster och höger cell är samma (båda 0 eller båda 1).
Eftersom det inte finns några celler före celler längst till vänster och efter celler längst till höger anses värdecellerna före cellerna längst till vänster och efter cellerna längst till höger alltid vara 0 (eller inaktiva).
Exempel:
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 enda viktiga är att se till att vi behåller en kopia av en given array eftersom vi behöver tidigare värden för att uppdatera för nästa dag. Nedan finns detaljerade steg.
- Först kopierar vi cellerna[]-arrayen till temp[]-arrayen och gör ändringar i temp[]-arrayen enligt givet villkor.
- I tillståndet anges att om den omedelbara vänstra och högra cellen i den i:te cellen antingen inaktiv eller aktiv nästa dag blir jag inaktiv, dvs. (celler[i-1] == 0 och celler[i+1] == 0) eller (celler[i-1] == 1 och celler[i+1] == 1) då celler[i] = 0 dessa villkor kan tillämpas med XOR av celler[i-1] och celler[i+1].
- För 0:e indexcellens temp[0] = 0^celler[1] och för (n-1):e indexcellens temp[n-1] = 0^celler[n-2].
- För index 1 till n-2 gör nu följande operation temp[i] = celler[i-1] ^ celler[i+1]
- Upprepa processen tills k dagar är slutförda.
Följande är implementeringen av ovanstående steg.
C++ // C++ program to count active and inactive cells after k // days #include using namespace std ; // 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 void activeAndInactive ( bool cells [] int n int k ) { // copy cells[] array into temp [] array bool temp [ n ]; for ( int 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 ( 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 ++ ) ( cells [ i ] == 1 ) ? active ++ : inactive ++ ; printf ( 'Active Cells = %d Inactive Cells = %d' active inactive ); } // Driver program to check the test case int main () { bool cells [] = { 0 1 0 1 0 1 0 1 }; int k = 3 ; int n = sizeof ( cells ) / sizeof ( cells [ 0 ]); activeAndInactive ( cells n k ); return 0 ; }
Java // 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.
Python3 # 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 ( cells n k ): # 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 ( 1 n - 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# // 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 // 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. ?>
JavaScript < 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
Tidskomplexitet: O(N*K) där N är storleken på en array och K är antalet dagar.
Hjälputrymme: O(N)
Den här artikeln har granskats av team geeksforgeeks. Om du har ett bättre tillvägagångssätt för detta problem, dela gärna.
