Latin Square
A Latin Square is a n x n grid filled by n distinct numbers each appearing exactly once in each row and column. Given an input n, we have to print a n x n matrix consisting of numbers from 1 to n each appearing exactly once in each row and each column.
Examples :
Input: 3 Output: 1 2 3 3 1 2 2 3 1 Input: 5 Output: 1 2 3 4 5 5 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1
Did you find any pattern in which the number is stored in a Latin Square?
- In the first row, the numbers are stored from 1 to n serially.
- In the second row, the numbers are shifted to the right by one column. i.e, 1 is stored at 2nd column now and so on.
- In the third row, the numbers are shifted to the right by two columns. i.e, 1 is stored at 3rd column now and so on.
- We continue the same way for the remaining rows.
Note: There may be more than one possible configuration of a n x n Latin square.
Implementation:
C++
// C++ program to print Latin Square #include <iostream> using namespace std; // Function to print n x n Latin Square void printLatin( int n) { // A variable to control the rotation // point. int k = n+1; // Loop to print rows for ( int i=1; i<=n; i++) { // This loops runs only after first // iteration of outer loop. It prints // numbers from n to k int temp = k; while (temp <= n) { cout << temp << " " ; temp++; } // This loop prints numbers from 1 to k-1. for ( int j=1; j<k; j++) cout << j << " " ; k--; cout << endl; } } // Driver program to test above function int main( void ) { int n = 5; // Invoking printLatin function printLatin(n); return 0; } // This code is contributed by kothavvsaakash. |
C
// C program to print Latin Square #include<stdio.h> // Function to print n x n Latin Square void printLatin( int n) { // A variable to control the rotation // point. int k = n+1; // Loop to print rows for ( int i=1; i<=n; i++) { // This loops runs only after first // iteration of outer loop. It prints // numbers from n to k int temp = k; while (temp <= n) { printf ( "%d " , temp); temp++; } // This loop prints numbers from 1 to k-1. for ( int j=1; j<k; j++) printf ( "%d " , j); k--; printf ( "\n" ); } } // Driver program to test above function int main( void ) { int n = 5; // Invoking printLatin function printLatin(n); return 0; } |
Java
// Java program to print Latin Square class GFG { // Function to print n x n Latin Square static void printLatin( int n) { // A variable to control the // rotation point. int k = n+ 1 ; // Loop to print rows for ( int i = 1 ; i <= n; i++) { // This loops runs only after // first iteration of outer // loop. It prints // numbers from n to k int temp = k; while (temp <= n) { System.out.print(temp + " " ); temp++; } // This loop prints numbers from // 1 to k-1. for ( int j = 1 ; j < k; j++) System.out.print(j + " " ); k--; System.out.println(); } } // Driver code public static void main (String[] args) { int n = 5 ; // Invoking printLatin function printLatin(n); } } // This code is contributed by Anant Agarwal. |
Python 3
# Python 3 program to print Latin Square # Function to print n x n Latin Square def printLatin(n): # A variable to control the # rotation point. k = n + 1 # Loop to print rows for i in range ( 1 , n + 1 , 1 ): # This loops runs only after first # iteration of outer loop. It prints # numbers from n to k temp = k while (temp < = n) : print (temp, end = " " ) temp + = 1 # This loop prints numbers # from 1 to k-1. for j in range ( 1 , k): print (j, end = " " ) k - = 1 print () # Driver Code n = 5 # Invoking printLatin function printLatin(n) # This code is contributed by R_Raj |
C#
// C# program to print Latin Square using System; class GFG { // Function to print n x n // Latin Square static void printLatin( int n) { // A variable to control the // rotation point. int k = n + 1; // Loop to print rows for ( int i = 1; i <= n; i++) { // This loops runs only after // first iteration of outer // loop. It prints numbers // from n to k int temp = k; while (temp <= n) { Console.Write(temp + " " ); temp++; } // This loop prints numbers from // 1 to k-1. for ( int j = 1; j < k; j++) Console.Write(j + " " ); k--; Console.WriteLine(); } } // Driver code public static void Main () { int n = 5; // Invoking printLatin function printLatin(n); } } // This code is contributed by KRV. |
PHP
<?php // PHP program to print Latin Square // Function to print n x n Latin Square function printLatin( $n ) { // A variable to control // the rotation point. $k = $n + 1; // Loop to print rows for ( $i = 1; $i <= $n ; $i ++) { // This loops runs only after // first iteration of outer loop. // It prints numbers from n to k $temp = $k ; while ( $temp <= $n ) { echo $temp , " " ; $temp ++; } // This loop prints numbers // from 1 to k-1. for ( $j = 1; $j < $k ; $j ++) echo $j , " " ; $k --; echo "\n" ; } } // Driver Code $n = 5; // Invoking printLatin function printLatin( $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to print Latin Square // Function to print n x n // Latin Square function printLatin(n) { // A variable to control the // rotation point. let k = n + 1; // Loop to print rows for (let i = 1; i <= n; i++) { // This loops runs only after // first iteration of outer // loop. It prints numbers // from n to k let temp = k; while (temp <= n) { document.write(temp + " " ); temp++; } // This loop prints numbers from // 1 to k-1. for (let j = 1; j < k; j++) document.write(j + " " ); k--; document.write( "</br>" ); } } let n = 5; // Invoking printLatin function printLatin(n); </script> |
Output
1 2 3 4 5 5 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1
Time Complexity: O(n*n)
Auxiliary Space: O(1)