Given two integers R and C, the task is to find the element at the Rth row and Cth column.
Pattern:
- First Element of ith row =
- Every element is a Arithmetic progression increasing difference where common difference is 1.
- Initial Difference Term =
Examples:
Input: R = 4, C = 4
Output: 25
Explanation:
Pattern of size 4 * 4 is –
1 3 6 10
2 5 9 14
4 8 13 19
7 12 18 25
Therefore, Element at Pat[4][4] = 25
Input: R = 3, C = 3
Output: 13
Explanation:
Pattern of size 3 * 3 is –
1 3 6
2 5 9
4 8 13
Therefore, element at Pat[3][3] = 13
Naive Approach: A simple solution is to generate the pattern matrix of size R * C and then finally return the element at the Rth row and Cth column.
Time Complexity: O(R*C)
Auxiliary Space: O(R*C)
Efficient Approach: The idea is to find the first term of the Rth row using the formulae and then finally compute the Cth term of that column using the help of loop.
Below is the implementation of the above approach:
C++
// C++ implementation to compute the // R'th row and C'th column of the // given pattern #include <bits/stdc++.h> using namespace std; // Function to compute the // R'th row and C'th column of the // given pattern int findValue( int R, int C) { // First element of a given row int k = (R * (R - 1)) / 2 + 1; int diff = R + 1; // Element in the given column for ( int i = 1; i < C; i++) { k = (k + diff); diff++; } return k; } // Driver Code int main() { int R = 4; int C = 4; // Function call int k = findValue(R, C); cout << k; return 0; } |
Java
// Java implementation to compute the // R'th row and C'th column of the // given pattern import java.io.*; class GFG{ // Function to compute the R'th // row and C'th column of the // given pattern static int findValue( int R, int C) { // First element of a given row int k = (R * (R - 1 )) / 2 + 1 ; int diff = R + 1 ; // Element in the given column for ( int i = 1 ; i < C; i++) { k = (k + diff); diff++; } return k; } // Driver code public static void main (String[] args) { int R = 4 ; int C = 4 ; // Function call int k = findValue(R, C); System.out.println(k); } } // This code is contributed by mohit kumar 29 |
Python3
# Python3 implementation to find the # R'th row and C'th column value in # the given pattern # Function to find the # R'th row and C'th column value in # the given pattern def findValue(R, C): # First element of a given row k = (R * (R - 1 )) / / 2 + 1 diff = R + 1 # Element in the given column for i in range ( 1 , C): k = (k + diff) diff + = 1 return k # Driver Code if __name__ = = "__main__" : R = 4 C = 4 k = findValue(R, C) print (k) |
C#
// C# implementation to compute the // R'th row and C'th column of the // given pattern using System; class GFG{ // Function to compute the R'th // row and C'th column of the // given pattern static int findValue( int R, int C) { // First element of a given row int k = (R * (R - 1)) / 2 + 1; int diff = R + 1; // Element in the given column for ( int i = 1; i < C; i++) { k = (k + diff); diff++; } return k; } // Driver code public static void Main() { int R = 4; int C = 4; // Function call int k = findValue(R, C); Console.Write(k); } } // This code is contributed by Code_Mech |
Javascript
<script> // Javascript implementation to compute the // R'th row and C'th column of the // given pattern // Function to compute the R'th // row and C'th column of the // given pattern function findValue(R, C) { // First element of a given row let k = (R * (R - 1)) / 2 + 1; let diff = R + 1; // Element in the given column for (let i = 1; i < C; i++) { k = (k + diff); diff++; } return k; } // Driver Code let R = 4; let C = 4; // Function call let k = findValue(R, C); document.write(k); </script> |
25
Time complexity : O(C), where C is the column number. The code iterates C times to find the value in the specified column.
Space complexity : O(1), as it only uses a few variables and arrays of constant size, which means the space required does not increase with increasing input size.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!