Naughty Luke

Easy
0/40
Average time to solve is 15m
profile
Contributed by
17 upvotes
Asked in companies
OracleAmazon

Problem statement

Luke, a naughty kid, went to a museum one day. He sees an ancient grid 'A' consisting of 'N' rows and 'N' columns. Each cell of a grid is coloured with either black or white.

Luke performs two sequential operations on the grid ‘A’. First, he twists the grid vertically around the center. After that, as the second operation, he changes the colours of all the cells. If the cell is white, it is changed to black and vice-versa.

The following drawings show the twist operation and the colour change operation, respectively :

The black colour is represented by '1' and white colour is represented by '0' here. You have to print the final grid.

Example : 
'N' = 2, 'A' = { {0, 1}, {0, 0} }.

After twisting, the grid looks like :
'A' =  { {1, 0}, {0, 0} }.

After changing the colours, the grid looks like :
'A' =  { {0, 1}, {1, 1} }.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T', which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer 'N' denoting the dimension of the grid.

The next 'N' lines contain 'N' space-separated integers denoting the colour of a cell.
Output format : 
For each test case, print 'N' lines containing 'N' space-separated integers denoting the colour of each cell of the final grid.

Print the output of each test case in a new line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 100.

Sum of 'N' ^ 2 over all the test cases is <= 10 ^ 4.

Time Limit: 1 sec
Sample Input 1 :
2
3
1 1 0
0 1 1
1 0 0
1
0
Sample Output 1 :
1 0 0
0 0 1
1 1 0
1
Explanation Of Sample Input 1 :
For test 1:
After twisting the grid looks like : { {0, 1, 1}, {1, 1, 0}, {0, 0, 1} }.
After changing the colour of cells the grid looks like : { {1, 0, 0}, {0, 0, 1}, {1, 1, 0} }.

For test 2:
After twisting the grid looks like : { {0} }.
After changing the colour of cells the grid looks like : { {1} }.
Sample Input 2 :
2
3
1 1 1
1 1 1
1 1 1
4
1 1 1 1
0 0 0 0
1 1 1 1
0 0 0 0
Sample Output 2 :
0 0 0
0 0 0
0 0 0
0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1
Hint

Simulate the problem statement.

Approaches (1)
Optimal

 

Approach :

 

  • We will swap the first half of a row with the second half and change the colours of all the cells in the row.
  • We will do this for each row one by one.


 

Algorithm:

 

  • Loop through all the rows from 'i' = 0 to 'i' = 'N' - 1 :
    • Loop through the cells in this from 'j' = 0 to 'j' = ceil ( 'N' / 2 ) - 1 :
      • Swap( 'A[ i ][ j ]', 'A[ i ][ N - j  - 1]' ).
      • Change the colour of 'A[ i ][ j ]'.
      • If ( 'j' is not equal to 'N' - 'j' - 1 ) :
        • Change the colour of 'A[ i ][ N - j - 1]'.
  • Return 'A'.
Time Complexity

O(N * N), where 'N' is the dimension of the grid.

 

Since we are going through the first half for each row, swapping and changing a cell's colour takes O(1) each. Hence, the total Time Complexity is O(N * N).

Space Complexity

O(1)
 

We have only used constant extra space. (We have made all the changes in the input grid). So, the Space Complexity is constant, i.e. O(1).

Code Solution
(100% EXP penalty)
Naughty Luke
Full screen
Console