Dado un entero positivo G , la tarea es encontrar el número de valores de K tal que la suma de los primeros N números a partir de K sea G , es decir, (K + (K + 1) + … + (K + N – 1 )) = G , donde N puede ser cualquier número entero positivo.
Ejemplos:
Entrada: G = 10
Salida: 2
Explicación:
Los siguientes son los posibles valores de K:
- K = 1 y N = 4: La suma de {1, 2, 3, 4} es 10(= G).
- K = 10 y N = 1: La suma de {10} es 10(= G).
Por lo tanto, hay dos valores posibles de K. Por lo tanto, imprima 2.
Entrada: G = 15
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es verificar todos y cada uno de los valores de K de 1 a G y, si se cumple la condición dada, luego contar este valor de K. Después de comprobar todos los valores posibles de K , imprima el recuento total.
Complejidad Temporal: O(G 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede resolver observando la relación matemática que para cualquier valor de K :
=> (K) + (K + 1) + (K + 2) + … + (K + N – 1) = G
=> N*K + (1 + 2 + 3 + 4+ … + N – 1) = G
=> G = N*K + (N*(N – 1))/2
Por lo tanto, el valor K = G/N – (N – 1)/2 . De la relación anterior, se puede concluir que el posible valor de K existe si y solo si:
- N es el factor de G , es decir, (G % N) == 0 .
- N debe ser impar, es decir, (N % 2) == 1 .
Siga los pasos a continuación para resolver el problema:
- Inicialice la variable, digamos contar como 0 que almacena el recuento resultante de valores de K .
- Iterar sobre un rango [1, √G] usando la variable i y realizando las siguientes tareas:
- Si g%i es igual a 0 , entonces si i no es igual a g/i , entonces si i%2 es igual a 1 , entonces agregue el valor de contar por 1 y si (g/i)%2 es igual a 1 , luego agregue el valor de contar por 1 .
- De lo contrario, si i%2 es igual a 1 , agregue el valor de count by 1 .
- Después de completar los pasos anteriores, imprima el valor del conteo como resultado.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the count the value
// of K such that sum of the first N
// numbers from K is G
void findValuesOfK(int g)
{
// Stores the total count of K
int count = 0;
// Iterate till square root of g
for (int i = 1; i * i <= g; i++) {
// If the number is factor of g
if (g % i == 0) {
// If the second factor is
// not equal to first factor
if (i != g / i) {
// Check if two factors
// are odd or not
if (i & 1) {
count++;
}
if ((g / i) & 1) {
count++;
}
}
// If second factor is the
// same as the first factor
// then check if the first
// factor is odd or not
else if (i & 1) {
count++;
}
}
}
// Print the resultant count
cout << count;
}
// Driver Code
int main()
{
int G = 125;
findValuesOfK(G);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
// Function to find the count the value
// of K such that sum of the first N
// numbers from K is G
static void findValuesOfK(int g)
{
// Stores the total count of K
int count = 0;
// Iterate till square root of g
for (int i = 1; i * i <= g; i++) {
// If the number is factor of g
if (g % i == 0) {
// If the second factor is
// not equal to first factor
if (i != g / i) {
// Check if two factors
// are odd or not
if (i % 2 == 1) {
count++;
}
if ((g / i) % 2 == 1) {
count++;
}
}
// If second factor is the
// same as the first factor
// then check if the first
// factor is odd or not
else if (i % 2 == 1) {
count++;
}
}
}
// Print the resultant count
System.out.println(count);
}
// Driver code
public static void main(String[] args)
{
int G = 125;
findValuesOfK(G);
}
}
// This code is contributed by Potta Lokesh
Python3
# Python 3 program for the above approach from math import sqrt # Function to find the count the value # of K such that sum of the first N # numbers from K is G def findValuesOfK(g): # Stores the total count of K count = 0 # Iterate till square root of g for i in range(1,int(sqrt(g)) + 1, 1): # If the number is factor of g if (g % i == 0): # If the second factor is # not equal to first factor if (i != g // i): # Check if two factors # are odd or not if (i & 1): count += 1 if ((g // i) & 1): count += 1 # If second factor is the # same as the first factor # then check if the first # factor is odd or not elif (i & 1): count += 1 # Print the resultant count print(count) # Driver Code if __name__ == '__main__': G = 125 findValuesOfK(G) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the count the value
// of K such that sum of the first N
// numbers from K is G
static void findValuesOfK(int g)
{
// Stores the total count of K
int count = 0;
// Iterate till square root of g
for(int i = 1; i * i <= g; i++)
{
// If the number is factor of g
if (g % i == 0)
{
// If the second factor is
// not equal to first factor
if (i != g / i)
{
// Check if two factors
// are odd or not
if (i % 2 == 1)
{
count++;
}
if ((g / i) % 2 == 1)
{
count++;
}
}
// If second factor is the
// same as the first factor
// then check if the first
// factor is odd or not
else if (i % 2 == 1)
{
count++;
}
}
}
// Print the resultant count
Console.WriteLine(count);
}
// Driver code
public static void Main()
{
int G = 125;
findValuesOfK(G);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// JavaScript program for the above approach
// Function to find the count the value
// of K such that sum of the first N
// numbers from K is G
function findValuesOfK(g)
{
// Stores the total count of K
var count = 0;
// Iterate till square root of g
for (var i = 1; i * i <= g; i++) {
// If the number is factor of g
if (g % i == 0) {
// If the second factor is
// not equal to first factor
if (i != g / i) {
// Check if two factors
// are odd or not
if (i % 2 == 1) {
count++;
}
if ((g / i) % 2 == 1) {
count++;
}
}
// If second factor is the
// same as the first factor
// then check if the first
// factor is odd or not
else if (i % 2 == 1) {
count++;
}
}
}
// Print the resultant count
document.write(count);
}
// Driver code
var G = 125;
findValuesOfK(G);
// This code is contributed by shivanisinghss2110
</script>
4
Complejidad temporal: O(√G)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kritirikhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA