Encuentre N en la array dada que sigue un patrón

Dada una array infinita llena con los números naturales como se muestra a continuación: 
 

1 2 4 7 . . .
3 5 8 . . . .
6 9 . . . . .
10  . . . . .
. . . . . . .

Además, dado un número entero N y la tarea es encontrar la fila y la columna del número entero N en la array dada.
Ejemplos: 
 

Input: N = 5
Output: 2 2
5 is present in the 2nd row 
and the 2nd column.

Input: N = 3
Output: 2 1

Planteamiento: Al observar el problema detenidamente, el número de fila se puede obtener restando primero x números naturales de N tales que satisfagan la condición N – (x * (x + 1)) / 2 ≥ 1 y el valor resultante será el número de fila requerido. 
Para obtener la columna correspondiente, agregue primero x números naturales a 1 de modo que satisfagan la condición 1 + (y * (y + 1)) / 2 ≤ A . Reste este valor resultante de N para obtener la brecha entre la base y el valor dado y nuevamente reste la brecha de y + 1 .
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the row and
// the column of the given integer
pair<int, int> solve(int n)
{
 
    int low = 1, high = 1e4, x = n, p = 0;
 
    // Binary search for the row number
    while (low <= high) {
        int mid = (low + high) / 2;
        int sum = (mid * (mid + 1)) / 2;
 
        // Condition to get the maximum
        // x that satisfies the criteria
        if (x - sum >= 1) {
            p = mid;
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
 
    int start = 1, end = 1e4, y = 1, q = 0;
 
    // Binary search for the column number
    while (start <= end) {
        int mid = (start + end) / 2;
        int sum = (mid * (mid + 1)) / 2;
 
        // Condition to get the maximum
        // y that satisfies the criteria
        if (y + sum <= n) {
            q = mid;
            start = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }
 
    // Get the row and the column number
    x = x - (p * (p + 1)) / 2;
    y = y + (q * (q + 1)) / 2;
    int r = x;
    int c = q + 1 - n + y;
 
    // Return the pair
    pair<int, int> ans = { r, c };
    return ans;
}
 
// Driver code
int main()
{
    int n = 5;
 
    pair<int, int> p = solve(n);
    cout << p.first << " " << p.second;
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
     
    // Function to return the row and
    // the column of the given integer
    static int[] solve(int n)
    {
        int low = 1, high = (int)1e4, x = n, p = 0;
     
        // Binary search for the row number
        while (low <= high)
        {
            int mid = (low + high) / 2;
            int sum = (mid * (mid + 1)) / 2;
     
            // Condition to get the maximum
            // x that satisfies the criteria
            if (x - sum >= 1)
            {
                p = mid;
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }
     
        int start = 1, end = (int)1e4, y = 1, q = 0;
     
        // Binary search for the column number
        while (start <= end)
        {
            int mid = (start + end) / 2;
            int sum = (mid * (mid + 1)) / 2;
     
            // Condition to get the maximum
            // y that satisfies the criteria
            if (y + sum <= n)
            {
                q = mid;
                start = mid + 1;
            }
            else
            {
                end = mid - 1;
            }
        }
     
        // Get the row and the column number
        x = x - (p * (p + 1)) / 2;
        y = y + (q * (q + 1)) / 2;
        int r = x;
        int c = q + 1 - n + y;
     
        // Return the pair
        int ans[] = { r, c };
        return ans;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int n = 5;
     
        int []p = solve(n);
        System.out.println(p[0] + " " + p[1]);
 
    }
}
 
// This code is contributed by AnkitRai01

Python3

# Python3 implementation of the approach
 
# Function to return the row and
# the column of the given integer
def solve(n):
 
    low = 1
    high = 10**4
    x, p = n, 0
 
    # Binary search for the row number
    while (low <= high):
        mid = (low + high) // 2
        sum = (mid * (mid + 1)) // 2
 
        # Condition to get the maximum
        # x that satisfies the criteria
        if (x - sum >= 1):
            p = mid
            low = mid + 1
        else :
            high = mid - 1
 
    start, end, y, q = 1, 10**4, 1, 0
 
    # Binary search for the column number
    while (start <= end):
        mid = (start + end) // 2
        sum = (mid * (mid + 1)) // 2
 
        # Condition to get the maximum
        # y that satisfies the criteria
        if (y + sum <= n):
            q = mid
            start = mid + 1
        else:
            end = mid - 1
 
    # Get the row and the column number
    x = x - (p * (p + 1)) // 2
    y = y + (q * (q + 1)) // 2
    r = x
    c = q + 1 - n + y
 
    # Return the pair
    return r, c
 
# Driver code
n = 5
 
r, c = solve(n)
print(r, c)
 
# This code is contributed by Mohit Kumar

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to return the row and
    // the column of the given integer
    static int[] solve(int n)
    {
        int low = 1, high = (int)1e4, x = n, p = 0;
     
        // Binary search for the row number
        while (low <= high)
        {
            int mid = (low + high) / 2;
            int sum = (mid * (mid + 1)) / 2;
     
            // Condition to get the maximum
            // x that satisfies the criteria
            if (x - sum >= 1)
            {
                p = mid;
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }
     
        int start = 1, end = (int)1e4, y = 1, q = 0;
     
        // Binary search for the column number
        while (start <= end)
        {
            int mid = (start + end) / 2;
            int sum = (mid * (mid + 1)) / 2;
     
            // Condition to get the maximum
            // y that satisfies the criteria
            if (y + sum <= n)
            {
                q = mid;
                start = mid + 1;
            }
            else
            {
                end = mid - 1;
            }
        }
     
        // Get the row and the column number
        x = x - (p * (p + 1)) / 2;
        y = y + (q * (q + 1)) / 2;
        int r = x;
        int c = q + 1 - n + y;
     
        // Return the pair
        int []ans = {r, c};
        return ans;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int n = 5;
     
        int []p = solve(n);
        Console.WriteLine(p[0] + " " + p[1]);
    }
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
// Javascript implementation of the approach
 
// Function to return the row and
    // the column of the given integer
function solve(n)
{
    let low = 1, high = 1e4, x = n, p = 0;
       
        // Binary search for the row number
        while (low <= high)
        {
            let mid = Math.floor((low + high) / 2);
            let sum = Math.floor((mid * (mid + 1)) / 2);
       
            // Condition to get the maximum
            // x that satisfies the criteria
            if (x - sum >= 1)
            {
                p = mid;
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }
       
        let start = 1, end = 1e4, y = 1, q = 0;
       
        // Binary search for the column number
        while (start <= end)
        {
            let mid = Math.floor((start + end) / 2);
            let sum = Math.floor((mid * (mid + 1)) / 2);
       
            // Condition to get the maximum
            // y that satisfies the criteria
            if (y + sum <= n)
            {
                q = mid;
                start = mid + 1;
            }
            else
            {
                end = mid - 1;
            }
        }
       
        // Get the row and the column number
        x = x - Math.floor((p * (p + 1)) / 2);
        y = y + Math.floor((q * (q + 1)) / 2);
        let r = x;
        let c = q + 1 - n + y;
       
        // Return the pair
        let ans = [ r, c ];
        return ans;
}
 
// Driver code
let n = 5;
let p = solve(n);
document.write(p[0] + " " + p[1]);
     
 
// This code is contributed by patel2127
</script>
Producción: 

2 2

 

Complejidad del tiempo: O(log(N))

Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por antipr0 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *