k일 후 활성 및 비활성 셀
크기가 n인 이진 배열이 주어지면 n > 3 . 배열의 true(또는 1) 값은 활성을 의미하고 false(또는 0) 값은 비활성을 의미합니다. 숫자 k가 주어지면 작업은 k일 후 활성 및 비활성 셀 수를 찾는 것입니다. 매일 후 i번째 셀의 상태는 왼쪽과 오른쪽 셀이 동일하지 않으면 활성화되고, 왼쪽과 오른쪽 셀이 동일하면(둘 다 0 또는 둘 다 1) 비활성화됩니다.
가장 왼쪽 셀 앞과 가장 오른쪽 셀 뒤에는 셀이 없으므로 가장 왼쪽 셀 앞과 가장 오른쪽 셀 뒤의 값 셀은 항상 0(또는 비활성)으로 간주됩니다.
예:
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 유일하게 중요한 것은 다음 날 업데이트하려면 이전 값이 필요하기 때문에 주어진 배열의 복사본을 유지하는 것입니다. 다음은 자세한 단계입니다.
- 먼저 세포[] 배열을 temp[] 배열에 복사하고 주어진 조건에 따라 temp[] 배열을 변경합니다.
- 조건에서는 i번째 셀의 바로 왼쪽 및 오른쪽 셀이 비활성이거나 활성 상태이면 다음날 i가 비활성 상태가 됩니다. (cells[i-1] == 0 및cells[i+1] == 0) 또는 (cells[i-1] == 1 및cells[i+1] == 1) thencells[i] = 0 이러한 조건은cells[i-1]과cells[i+1]의 XOR을 사용하여 적용할 수 있습니다.
- 0번째 인덱스 셀의 경우 temp[0] = 0^cells[1]이고 (n-1)번째 인덱스 셀의 경우 temp[n-1] = 0^cells[n-2]입니다.
- 이제 인덱스 1에서 n-2에 대해 다음 작업을 수행합니다. temp[i] =cells[i-1]^cells[i+1]
- k일이 완료될 때까지 이 과정을 반복합니다.
다음은 위 단계의 구현입니다.
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>
산출
Active Cells = 2 Inactive Cells = 6
시간 복잡도: 오(N*K) 여기서 N은 배열의 크기이고 K는 일 수입니다.
보조공간 : O(N)
이 기사는 geeksforgeeks 팀이 검토했습니다. 이 문제에 대한 더 나은 접근 방식이 있으면 공유해 주세요.
