Encuentre el elemento en la array generada por las reglas dadas

Dadas algunas reglas para generar una array N × N mat[][] y dos enteros R y C , la tarea es encontrar el elemento en la ^fila R y ^la columna C. Las reglas son las siguientes: 

1. La primera fila es una serie AP que comienza con 1 y d = 1 (diferencia común).
2. Para todos los elementos en (i, j) tales que i > j , su valor es 0 .
3. El resto de los elementos siguen, Element(i, j) = Element(i – 1, j) + Element(i – 1, j – 1) .

Ejemplos: 
 

Entrada: N = 4, R = 3, C = 4 
Salida: 12 
mat[][] = 
{1, 2, 3, 4}, 
{0, 3, 5, 7}, 
{0, 0, 8, 12 }, 
{0, 0, 0, 20} 
y el elemento en la tercera fila y cuarta columna es 12.
Entrada: N = 2, R = 2, C = 2 
Salida: 3 
 

Acercarse: 

• La clave básica es observar el patrón, la primera observación es que cada fila tendrá un AP después del elemento en (i, i) . La diferencia común para el número de fila j es pow(2, j – 1) .
• Ahora necesitamos encontrar el primer término de cada fila para encontrar cualquier elemento (R, C) . Si consideramos solo los elementos iniciales en cada fila (es decir, el elemento en la diagonal), podemos observar que es igual a (R + 1) * pow(2, R – 2) para cada fila R de 2 a N.
• Entonces, si R > C , entonces el elemento es 0 , de lo contrario , C – R es la posición del elemento requerido en AP que está presente en la R ^-ésima fila para la cual ya conocemos el término inicial y la diferencia común. Entonces, podemos encontrar el elemento como inicio + d * (C – R) .

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the element in the rth row
// and cth column from the required matrix
int getElement(int N, int r, int c)
{
 
    // Condition for lower half of matrix
    if (r > c)
        return 0;
 
    // Condition if element is in first row
    if (r == 1) {
        return c;
    }
 
    // Starting element of AP in row r
    int a = (r + 1) * pow(2, r - 2);
 
    // Common difference of AP in row r
    int d = pow(2, r - 1);
 
    // Position of element to find
    // in AP in row r
    c = c - r;
 
    int element = a + d * c;
 
    return element;
}
 
// Driver Code
int main()
{
    int N = 4, R = 3, C = 4;
 
    cout << getElement(N, R, C);
 
    return 0;
}

// Java implementation of the above approach
import java.io.*;
import java.util.*;
 
class GFG
{
     
// Function to return the element
// in the rth row and cth column
// from the required matrix
static int getElement(int N, int r, int c)
{
 
    // Condition for lower half of matrix
    if (r > c)
        return 0;
 
    // Condition if element is in first row
    if (r == 1)
    {
        return c;
    }
 
    // Starting element of AP in row r
    int a = (r + 1) * (int)(Math.pow(2,(r - 2)));
 
    // Common difference of AP in row r
    int d = (int)(Math.pow(2,(r - 1)));
 
    // Position of element to find
    // in AP in row r
    c = c - r;
 
    int element = a + d * c;
 
    return element;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 4, R = 3, C = 4;
 
    System.out.println(getElement(N, R, C));
}
}
 
// This code is contributed by Krikti

# Python3 implementation of the approach
 
# Function to return the element in the rth row
# and cth column from the required matrix
def getElement(N, r, c) :
 
    # Condition for lower half of matrix
    if (r > c) :
        return 0;
 
    # Condition if element is in first row
    if (r == 1) :
        return c;
     
 
    # Starting element of AP in row r
    a = (r + 1) * pow(2, r - 2);
 
    # Common difference of AP in row r
    d = pow(2, r - 1);
 
    # Position of element to find
    # in AP in row r
    c = c - r;
 
    element = a + d * c;
 
    return element;
 
 
# Driver Code
if __name__ == "__main__" :
 
    N = 4; R = 3; C = 4;
 
    print(getElement(N, R, C));
     
# This Code is contributed by AnkitRai01

// C# implementation of the above approach
using System;
     
class GFG
{
     
// Function to return the element
// in the rth row and cth column
// from the required matrix
static int getElement(int N, int r, int c)
{
 
    // Condition for lower half of matrix
    if (r > c)
        return 0;
 
    // Condition if element is in first row
    if (r == 1)
    {
        return c;
    }
 
    // Starting element of AP in row r
    int a = (r + 1) * (int)(Math.Pow(2,(r - 2)));
 
    // Common difference of AP in row r
    int d = (int)(Math.Pow(2,(r - 1)));
 
    // Position of element to find
    // in AP in row r
    c = c - r;
 
    int element = a + d * c;
 
    return element;
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 4, R = 3, C = 4;
 
    Console.WriteLine(getElement(N, R, C));
}
}
 
// This code is contributed by Princi Singh

<script>
// Java script implementation of the above approach
     
// Function to return the element
// in the rth row and cth column
// from the required matrix
function getElement( N,  r,  c)
{
 
    // Condition for lower half of matrix
    if (r > c)
        return 0;
 
    // Condition if element is in first row
    if (r == 1)
    {
        return c;
    }
 
    // Starting element of AP in row r
    let a = (r + 1) * parseInt(Math.pow(2,(r - 2)));
 
    // Common difference of AP in row r
    let d = parseInt(Math.pow(2,(r - 1)));
 
    // Position of element to find
    // in AP in row r
    c = c - r;
 
    let element = a + d * c;
 
    return element;
}
 
// Driver Code
    let N = 4, R = 3, C = 4;
 
    document.write(getElement(N, R, C));
 
//contributed by bobby
 
</script>

12

Complejidad de tiempo: O (logr)

Espacio Auxiliar: O(1)