Considere la secuencia infinita de números enteros: 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5…. La secuencia se construye de la siguiente manera: primero se escribe el número 1, luego los números del 1 al 2, luego los números del 1 al 3, luego los números del 1 al 4, y así sucesivamente. Encuentra el número en la n-ésima posición de la secuencia.
Ejemplos:
Input : n = 3 Output : 2 The 3rd number in the sequence is 2. Input : 55 Output : 10
Primer enfoque: la idea es encontrar primero el número de bloque de n. Para determinar el bloque con el número n-ésimo, primero restamos 1 (recuento de elementos en el primer bloque) de n, luego restamos 2, luego restamos 3 y así sucesivamente hasta obtener n negativo. El número de sustracciones será el número del bloque y la posición en el bloque será el último número no negativo que obtendremos.
C++
// CPP program to find the
// value at n-th place in
// the given sequence
#include <bits/stdc++.h>
using namespace std;
// Returns n-th number in sequence
// 1, 1, 2, 1, 2, 3, 1, 2, 4, ...
int findNumber(int n)
{
n--;
// One by one subtract counts
// elements in different blocks
int i = 1;
while (n >= 0)
{
n -= i;
++i;
}
return (n + i);
}
// Driver code
int main()
{
int n = 3;
cout << findNumber(n) << endl;
return 0;
}
Java
// Java program to find the
// value at n-th place in
// the given sequence
import java.io.*;
class GFG
{
// Returns n-th number in sequence
// 1, 1, 2, 1, 2, 3, 1, 2, 4, ...
static int findNumber(int n)
{
n--;
// One by one subtract counts
// elements in different blocks
int i = 1;
while (n >= 0)
{
n -= i;
++i;
}
return (n + i);
}
// Driver Code
public static void main(String[] args)
{
int n = 3;
System.out.println(findNumber(n));
}
}
// This code is contributed by Ajit.
Python3
# Python code to find the value at # n-th place in the given sequence # Returns n-th number in sequence # 1, 1, 2, 1, 2, 3, 1, 2, 4, ... def findNumber( n ): n -= 1 # One by one subtract counts # elements in different blocks i = 1 while n >= 0: n -= i i += 1 return (n + i) # Driver code n = 3 print(findNumber(n)) # This code is contributed # by "Sharad_Bhardwaj".
C#
// C# program to find the
// value at n-th place in
// the given sequence
using System;
class GFG
{
// Returns n-th number in sequence
// 1, 1, 2, 1, 2, 3, 1, 2, 4, ...
static int findNumber(int n)
{
n--;
// One by one subtract counts
// elements in different blocks
int i = 1;
while (n >= 0)
{
n -= i;
++i;
}
return (n + i);
}
// Driver code
public static void Main()
{
int n = 3;
Console.WriteLine(findNumber(n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find the
// value at n-th place in
// the given sequence
// Returns n-th number in sequence
// 1, 1, 2, 1, 2, 3, 1, 2, 4, ...
function findNumber( $n)
{
$n--;
// One by one subtract counts
// elements in different blocks
$i = 1;
while ($n >= 0)
{
$n -= $i;
++$i;
}
return ($n + $i);
}
// Driver code
$n = 3;
echo findNumber($n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find the
// value at n-th place in
// the given sequence
// Returns n-th number in sequence
// 1, 1, 2, 1, 2, 3, 1, 2, 4, ...
function findNumber(n)
{
n--;
// One by one subtract counts
// elements in different blocks
let i = 1;
while (n >= 0)
{
n -= i;
++i;
}
return (n + i);
}
// Driver code
let n = 3;
document.write(findNumber(n));
// This code is contributed by mukesh07.
</script>
2
Complejidad temporal: O(√n), Espacio auxiliar: -O(1)
Segundo Enfoque: La respuesta a la Sucesión Infinita puede hacerse en O(1). Podemos organizar la secuencia como: 1 (1). Eso significa las posiciones que el primero en esa línea es 1, 2 (2) 1, 2, 3 (4) 1, 2, 3, 4 (7) 1, 2, 3, 4, 5 (11) Luego tendría una nueva secuencia, que es mucho más fácil de encontrar. 1 (1) 2 (2) 4 (3) 7 (4) 11 El número entre paréntesis es la distancia entre el número de la nueva secuencia.
Para encontrar la base del número, necesitamos resolver la ecuación n = x(x+1)/2 + 1 [O x^2 + x + 2 – 2n = 0]. Necesitamos aislar x (obtener el valor mínimo máximo).
Luego usamos la x que obtuvimos en la misma fórmula, pero ahora el resultado será la base de la línea. Solo necesitamos calcular la distancia entre el número que recibimos como entrada y el número que obtuvimos como base.
n — base + 1
C++
// CPP program to find the
// value at n-th place in
// the given sequence
#include <bits/stdc++.h>
using namespace std;
// Definition of findNumber
// function
int findNumber(int n)
{
// Finding x from equation
// n = x(x + 1)/2 + 1
int x = (int)floor((-1 +
sqrt(1 + 8 * n - 8)) / 2);
// Base of current block
int base = (x * (x + 1)) / 2 + 1;
// Value of n-th element
return n - base + 1;
}
// Driver code
int main()
{
int n = 55;
cout << findNumber(n) << endl;
return 0;
}
Java
// Java program to find the
// value at n-th place in
// the given sequence
import java.io.*;
class GFG
{
// Definition of findNumber function
static int findNumber(int n)
{
// Finding x from equation
// n = x(x + 1)/2 + 1
int x = (int)Math.floor((-1 +
Math.sqrt(1 + 8 * n - 8)) / 2);
// Base of current block
int base = (x * (x + 1)) / 2 + 1;
// Value of n-th element
return n - base + 1;
}
// Driver code
public static void main(String[] args)
{
int n = 55;
System.out.println(findNumber(n));
}
}
// This code is contributed by Ajit.
Python3
# Python program to find # the value at n-th place # in the given sequence import math # Definition of findNumber function def findNumber( n ): # Finding x from equation # n = x(x + 1)/2 + 1 x = int(math.floor((-1 + math.sqrt(1 + 8 * n - 8)) / 2)) # Base of current block base = (x * (x + 1)) / 2 + 1 # Value of n-th element return n - base + 1 # Driver code n = 55 print(findNumber(n)) # This code is contributed # by "Abhishek Sharma 44"
C#
// C# program to find the
// value at n-th place in
// the given sequence
using System;
class GFG
{
// Definition of findNumber function
static int findNumber(int n)
{
// Finding x from equation
// n = x(x + 1)/2 + 1
int x = (int)Math.Floor((-1 +
Math.Sqrt(1 + 8 * n - 8)) / 2);
// Base of current block
int Base = (x * (x + 1)) / 2 + 1;
// Value of n-th element
return n - Base + 1;
}
// Driver code
public static void Main()
{
int n = 55;
Console.WriteLine(findNumber(n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find the
// value at n-th place in
// the given sequence
// Definition of findNumber function
function findNumber($n)
{
// Finding x from equation
// n = x(x + 1)/2 + 1
$x = floor((-1 + sqrt(1 +
8 * $n - 8)) / 2);
// Base of current block
$base = ($x * ($x + 1)) / 2 + 1;
// Value of n-th element
return $n - $base + 1;
}
// Driver code
$n = 55;
echo findNumber($n) ;
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find the
// value at n-th place in
// the given sequence
// Definition of findNumber
// function
function findNumber(n)
{
// Finding x from equation
// n = x(x + 1)/2 + 1
let x = Math.floor((-1 + Math.sqrt(1 + 8 * n - 8)) / 2);
// Base of current block
let base = (x * (x + 1)) / 2 + 1;
// Value of n-th element
return n - base + 1;
}
let n = 55;
document.write(findNumber(n));
// This code is contributed by suresh07.
</script>
10
Complejidad de tiempo: O(1)
Espacio Auxiliar :O(1)
Este artículo es una contribución de Sagar Shukla . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA