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)