Dado un número N. La tarea es imprimir todos los números consecutivos posibles que suman N.
Ejemplos:
Input: N = 100 Output: 9 10 11 12 13 14 15 16 18 19 20 21 22 Input: N = 125 Output: 8 9 10 11 12 13 14 15 16 17 23 24 25 26 27 62 63
Un hecho importante es que no podemos encontrar números consecutivos por encima de N/2 que sumen N, porque N/2 + (N/2 + 1) sería más que N. Así que empezamos desde el inicio = 1 hasta el final = N/ 2 y verifique para cada secuencia consecutiva si suma N o no. Si es así, imprimimos esa secuencia y comenzamos a buscar la siguiente secuencia incrementando el punto de inicio.
C++
// C++ program to print consecutive sequences
// that add to a given value
#include<bits/stdc++.h>
using namespace std;
void findConsecutive(int N)
{
// Note that we don't ever have to sum
// numbers > ceil(N/2)
int start = 1, end = (N+1)/2;
// Repeat the loop from bottom to half
while (start < end)
{
// Check if there exist any sequence
// from bottom to half which adds up to N
int sum = 0;
for (int i = start; i <= end; i++)
{
sum = sum + i;
// If sum = N, this means consecutive
// sequence exists
if (sum == N)
{
// found consecutive numbers! print them
for (int j = start; j <= i; j++)
cout <<" "<< j;
cout <<"\n";
break;
}
// if sum increases N then it can not exist
// in the consecutive sequence starting from
// bottom
if (sum > N)
break;
}
sum = 0;
start++;
}
}
// Driver code
int main(void)
{
int N = 125;
findConsecutive(N);
return 0;
}
// This code is contributed by shivanisinghss2110
C
// C++ program to print consecutive sequences
// that add to a given value
#include<stdio.h>
void findConsecutive(int N)
{
// Note that we don't ever have to sum
// numbers > ceil(N/2)
int start = 1, end = (N+1)/2;
// Repeat the loop from bottom to half
while (start < end)
{
// Check if there exist any sequence
// from bottom to half which adds up to N
int sum = 0;
for (int i = start; i <= end; i++)
{
sum = sum + i;
// If sum = N, this means consecutive
// sequence exists
if (sum == N)
{
// found consecutive numbers! print them
for (int j = start; j <= i; j++)
printf("%d ", j);
printf("\n");
break;
}
// if sum increases N then it can not exist
// in the consecutive sequence starting from
// bottom
if (sum > N)
break;
}
sum = 0;
start++;
}
}
// Driver code
int main(void)
{
int N = 125;
findConsecutive(N);
return 0;
}
Java
// Java program to print
// consecutive sequences
// that add to a given value
import java.io.*;
class GFG
{
static void findConsecutive(int N)
{
// Note that we don't
// ever have to sum
// numbers > ceil(N/2)
int start = 1;
int end = (N + 1) / 2;
// Repeat the loop
// from bottom to half
while (start < end)
{
// Check if there exist
// any sequence from
// bottom to half which
// adds up to N
int sum = 0;
for (int i = start; i <= end; i++)
{
sum = sum + i;
// If sum = N, this means
// consecutive sequence exists
if (sum == N)
{
// found consecutive
// numbers! print them
for (int j = start; j <= i; j++)
System.out.print(j + " ");
System.out.println();
break;
}
// if sum increases N then
// it can not exist in the
// consecutive sequence
// starting from bottom
if (sum > N)
break;
}
sum = 0;
start++;
}
}
// Driver code
public static void main (String[] args)
{
int N = 125;
findConsecutive(N);
}
}
// This code is contributed by m_kit
Python3
# Python3 program to print consecutive # sequences that add to a given value def findConsecutive(N): # Note that we don't ever have to # Sum numbers > ceil(N/2) start = 1 end = (N + 1) // 2 # Repeat the loop from bottom to half while (start < end): # Check if there exist any sequence # from bottom to half which adds up to N Sum = 0 for i in range(start, end + 1): Sum = Sum + i # If Sum = N, this means consecutive # sequence exists if (Sum == N): # found consecutive numbers! print them for j in range(start, i + 1): print(j, end = " ") print() break # if Sum increases N then it can not # exist in the consecutive sequence # starting from bottom if (Sum > N): break Sum = 0 start += 1 # Driver code N = 125 findConsecutive(N) # This code is contributed by Mohit kumar 29
C#
// C# program to print
// consecutive sequences
// that add to a given value
using System;
class GFG
{
static void findConsecutive(int N)
{
// Note that we don't
// ever have to sum
// numbers > ceil(N/2)
int start = 1;
int end = (N + 1) / 2;
// Repeat the loop
// from bottom to half
while (start < end)
{
// Check if there exist
// any sequence from
// bottom to half which
// adds up to N
int sum = 0;
for (int i = start; i <= end; i++)
{
sum = sum + i;
// If sum = N, this means
// consecutive sequence exists
if (sum == N)
{
// found consecutive
// numbers! print them
for (int j = start; j <= i; j++)
Console.Write(j + " ");
Console.WriteLine();
break;
}
// if sum increases N then
// it can not exist in the
// consecutive sequence
// starting from bottom
if (sum > N)
break;
}
sum = 0;
start++;
}
}
// Driver code
static public void Main ()
{
int N = 125;
findConsecutive(N);
}
}
// This code is contributed by ajit
PHP
<?php
// PHP program to print consecutive
// sequences that add to a given value
function findConsecutive($N)
{
// Note that we don't ever have
// to sum numbers > ceil(N/2)
$start = 1;
$end = ($N + 1) / 2;
// Repeat the loop from
// bottom to half
while ($start < $end)
{
// Check if there exist any
// sequence from bottom to
// half which adds up to N
$sum = 0;
for ($i = $start; $i <= $end; $i++)
{
$sum = $sum + $i;
// If sum = N, this means
// consecutive sequence exists
if ($sum == $N)
{
// found consecutive
// numbers! print them
for ($j = $start; $j <= $i; $j++)
echo $j ," ";
echo "\n";
break;
}
// if sum increases N then it
// can not exist in the consecutive
// sequence starting from bottom
if ($sum > $N)
break;
}
$sum = 0;
$start++;
}
}
// Driver code
$N = 125;
findConsecutive($N);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to print consecutive sequences
// that add to a given value
function findConsecutive( N)
{
// Note that we don't ever have to sum
// numbers > ceil(N/2)
let start = 1, end = Math.trunc((N+1)/2);
// Repeat the loop from bottom to half
while (start < end)
{
// Check if there exist any sequence
// from bottom to half which adds up to N
let sum = 0;
for (let i = start; i <= end; i++)
{
sum = sum + i;
// If sum = N, this means consecutive
// sequence exists
if (sum == N)
{
// found consecutive numbers! print them
for (let j = start; j <= i; j++)
document.write(j+" ");
document.write("<br/>");
break;
}
// if sum increases N then it can not exist
// in the consecutive sequence starting from
// bottom
if (sum > N)
break;
}
sum = 0;
start++;
}
}
// Driver program
let N = 125;
findConsecutive(N);
</script>
Producción :
8 9 10 11 12 13 14 15 16 17 23 24 25 26 27 62 63
Solución optimizada:
en la solución anterior, seguimos recalculando las sumas de principio a fin, lo que da como resultado una complejidad temporal O(N^2) en el peor de los casos. Esto se puede evitar mediante el uso de una array de sumas precalculadas, o mejor aún, simplemente haciendo un seguimiento de la suma que tiene hasta ahora y ajustándola dependiendo de cómo se compare con la suma deseada.
La complejidad del tiempo del siguiente código es O (N).
C++
// Optimized C++ program to find sequences of all consecutive
// numbers with sum equal to N
#include <bits/stdc++.h>
using namespace std;
void printSums(int N)
{
int start = 1, end = 1;
int sum = 1;
while (start <= N/2)
{
if (sum < N)
{
end += 1;
sum += end;
}
else if (sum > N)
{
sum -= start;
start += 1;
}
else if (sum == N)
{
for (int i = start; i <= end; ++i)
cout <<" "<< i;
cout <<"\n";
sum -= start;
start += 1;
}
}
}
// Driver Code
int main()
{
printSums(125);
return 0;
}
// this code is contributed by shivanisinghss2110
C
// Optimized C program to find sequences of all consecutive
// numbers with sum equal to N
#include <stdio.h>
void printSums(int N)
{
int start = 1, end = 1;
int sum = 1;
while (start <= N/2)
{
if (sum < N)
{
end += 1;
sum += end;
}
else if (sum > N)
{
sum -= start;
start += 1;
}
else if (sum == N)
{
for (int i = start; i <= end; ++i)
printf("%d ", i);
printf("\n");
sum -= start;
start += 1;
}
}
}
// Driver Code
int main()
{
printSums(125);
return 0;
}
Java
// Optimized Java program to find
// sequences of all consecutive
// numbers with sum equal to N
import java.io.*;
class GFG {
static void printSums(int N)
{
int start = 1, end = 1;
int sum = 1;
while (start <= N/2)
{
if (sum < N)
{
end += 1;
sum += end;
}
else if (sum > N)
{
sum -= start;
start += 1;
}
else if (sum == N)
{
for (int i = start;
i <= end; ++i)
System.out.print(i
+ " ");
System.out.println();
sum -= start;
start += 1;
}
}
}
// Driver Code
public static void main (String[] args)
{
printSums(125);
}
}
// This code is contributed by anuj_67.
Python3
# Optimized Python3 program to find sequences of all consecutive # numbers with sum equal to N def findConsecutive(N): start = 1 end = 1 sum = 1 while start <= N/2: if sum < N: end += 1 sum += end if sum > N: sum -= start start += 1 if sum == N: for i in range(start, end + 1): print(i, end=' ') print( ) sum -= start start += 1 # Driver code N = 125 findConsecutive(N) # This code is contributed by Sanskriti Agrawal
C#
// Optimized C# program to find
// sequences of all consecutive
// numbers with sum equal to N
using System;
class GFG {
static void printSums(int N)
{
int start = 1, end = 1;
int sum = 1;
while (start <= N/2)
{
if (sum < N)
{
end += 1;
sum += end;
}
else if (sum > N)
{
sum -= start;
start += 1;
}
else if (sum == N)
{
for (int i = start;
i <= end; ++i)
Console.Write(i
+ " ");
Console.WriteLine();
sum -= start;
start += 1;
}
}
}
// Driver Code
public static void Main ()
{
printSums(125);
}
}
// This code is contributed by anuj_67.
PHP
<?php
// Optimized PHP program to find
// sequences of all consecutive
// numbers with sum equal to N
function printSums($N)
{
$start = 1; $end = 1;
$sum = 1;
while ($start <= $N / 2)
{
if ($sum < $N)
{
$end += 1;
$sum += $end;
}
else if ($sum > $N)
{
$sum -= $start;
$start += 1;
}
else if ($sum == $N)
{
for ($i = $start; $i <= $end; ++$i)
echo $i," ";
echo "\n";
$sum -= $start;
$start += 1;
}
}
}
// Driver Code
printSums(125);
// This code is contributed by jit_t
?>
Javascript
<script>
// Javascript program to find
// sequences of all consecutive
// numbers with sum equal to N
function printSums(N)
{
let start = 1, end = 1;
let sum = 1;
while (start <= N / 2)
{
if (sum < N)
{
end += 1;
sum += end;
}
else if (sum > N)
{
sum -= start;
start += 1;
}
else if (sum == N)
{
for(let i = start;
i <= end; ++i)
document.write(i + " ");
document.write("<br/>");
sum -= start;
start += 1;
}
}
}
// Driver code
printSums(125);
// This code is contributed by splevel62
</script>
Producción :
8 9 10 11 12 13 14 15 16 17 23 24 25 26 27 62 63
Referencia:
https://www.careercup.com/page?pid=microsoft-interview-questions&n=2
Este artículo es una contribución de Niteesh Kumar . 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