Dado un número entero N , la tarea es encontrar el número total de formas en que se puede formar una secuencia que consiste en números enteros impares consecutivos distintos que suman N .
Ejemplos :
Entrada : N = 45
Salida : 3
Explicación : 3 formas de elegir distintos números impares consecutivos que suman 45 son:
{5, 7, 9, 11, 13}, {13, 15, 17} y {45}.Entrada : N = 20
Salida : 1
Explicación : 9 y 11 son los únicos números impares consecutivos cuya suma es 20
Enfoque: La idea para resolver el problema se basa en la idea de la suma de los primeros K enteros impares consecutivos :
- La suma de los primeros K enteros impares consecutivos es K 2 .
- Sea una secuencia de enteros impares consecutivos desde (y+1)-ésimo número impar hasta x -ésimo número impar (x > y) , cuya suma es N.
- Entonces, x 2 – y 2 = N o (x + y) * (x – y) = N .
- Sean a y b dos divisores de N. Por lo tanto, a * b=N .
- Por lo tanto, x + y = a & x – y = b
- Resolviendo estos dos, obtenemos x = (a + b) / 2 .
- Esto implica que si (a + b) es par, entonces x e y serían integrales, lo que significa que existiría una secuencia de enteros impares consecutivos que suman N .
Siga los pasos mencionados a continuación para implementar la observación anterior:
- Iterar a través de todos los pares de divisores, de modo que su producto sea N .
- Si la suma de dicho par de divisores es par, incrementa la cuenta de respuesta en 1.
- Devuelve el recuento final al final.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// Number of sequence of odd integers that
// Contains distinct consecutive odd integers
// That add up to N.
int numberOfSequences(int N)
{
// Initializing count variable by 0,
// That stores the number of sequences
int count = 0;
// Iterating through all divisors of N
for (int i = 1; i * i <= N; i++) {
if (N % i == 0) {
// If sum of the two divisors
// Is even, we increment
// The count by 1
int divisor1 = i;
int divisor2 = N / i;
int sum = divisor1 + divisor2;
if (sum % 2 == 0) {
count++;
}
}
}
// Returning total count
// After completing the iteration
return count;
}
// Driver Code
int main()
{
int N = 45;
// Function call
int number_of_sequences = numberOfSequences(N);
cout << number_of_sequences;
return 0;
}
Java
// JAVA program to check whether sum
// Is equal to target value
// After K operations
import java.util.*;
class GFG
{
// Function to calculate
// Number of sequence of odd integers that
// Contains distinct consecutive odd integers
// That add up to N.
static int numberOfSequences(int N)
{
// Initializing count variable by 0,
// That stores the number of sequences
int count = 0;
// Iterating through all divisors of N
for (int i = 1; i * i <= N; i++) {
if (N % i == 0) {
// If sum of the two divisors
// Is even, we increment
// The count by 1
int divisor1 = i;
int divisor2 = N / i;
int sum = divisor1 + divisor2;
if (sum % 2 == 0) {
count++;
}
}
}
// Returning total count
// After completing the iteration
return count;
}
// Driver Code
public static void main(String[] args)
{
int N = 45;
// Function call
int number_of_sequences = numberOfSequences(N);
System.out.print(number_of_sequences);
}
}
// This code is contributed by sanjoy_62.
Python3
# Python code for the above approach import math # Function to calculate # Number of sequence of odd integers that # Contains distinct consecutive odd integers # That add up to N. def numberOfSequences(N): # Initializing count variable by 0, # That stores the number of sequences count = 0; # Iterating through all divisors of N for i in range(1,math.ceil(math.sqrt(N))): if (N % i == 0): # If sum of the two divisors # Is even, we increment # The count by 1 divisor1 = i; divisor2 = N //i; sum = divisor1 + divisor2; if (sum % 2 == 0): count = count + 1 # Returning total count # After completing the iteration return count; # Driver Code N = 45; # Function call number_of_sequences = numberOfSequences(N); print(number_of_sequences); # This code is contributed by Potta Lokesh
C#
// C# program for above approach:
using System;
class GFG {
// Function to calculate
// Number of sequence of odd integers that
// Contains distinct consecutive odd integers
// That add up to N.
static int numberOfSequences(int N)
{
// Initializing count variable by 0,
// That stores the number of sequences
int count = 0;
// Iterating through all divisors of N
for (int i = 1; i * i <= N; i++) {
if (N % i == 0) {
// If sum of the two divisors
// Is even, we increment
// The count by 1
int divisor1 = i;
int divisor2 = N / i;
int sum = divisor1 + divisor2;
if (sum % 2 == 0) {
count++;
}
}
}
// Returning total count
// After completing the iteration
return count;
}
// Driver Code
public static void Main()
{
int N = 45;
// Function call
int number_of_sequences = numberOfSequences(N);
Console.Write(number_of_sequences);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program for above approach:
// Function to calculate
// Number of sequence of odd integers that
// Contains distinct consecutive odd integers
// That add up to N.
const numberOfSequences = (N) => {
// Initializing count variable by 0,
// That stores the number of sequences
let count = 0;
// Iterating through all divisors of N
for (let i = 1; i * i <= N; i++) {
if (N % i == 0) {
// If sum of the two divisors
// Is even, we increment
// The count by 1
let divisor1 = i;
let divisor2 = parseInt(N / i);
let sum = divisor1 + divisor2;
if (sum % 2 == 0) {
count++;
}
}
}
// Returning total count
// After completing the iteration
return count;
}
// Driver Code
let N = 45;
// Function call
let number_of_sequences = numberOfSequences(N);
document.write(number_of_sequences);
// This code is contributed by rakeshsahni
</script>
Producción
3
Complejidad de Tiempo : O(√N)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por kamabokogonpachiro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA