Verifique se N pode ser dividido em K elementos consecutivos com uma soma igual a N
Dado um inteiro N , a nossa tarefa é verificar se N pode ser dividido em K elementos consecutivos com uma soma igual a N. Imprimir -1 se não for possível dividir desta maneira, caso contrário, imprimir o valor K .
Exemplos:
Entrada: N = 12
Saída: 3
Explicação:
O inteiro N = 12 pode ser dividido em 3 elementos consecutivos {3, 4, 5} onde 3 + 4 + 5 = 12.
Entrada: N = 8
Saída: -1
Explicação:
Não tal divisão do inteiro 8 é possível.
Abordagem: Para resolver o problema mencionado acima, vamos dividir o inteiro N em i números consecutivos. Os termos da sequência serão semelhantes a (d + 1), (d + 2), (d + 3) ... (d + i) onde d é a diferença comum presente em cada um dos inteiros e a soma destes sequência deve ser igual a N .
Portanto, a soma desses números também pode ser expressa como:
Como a soma = i * (i + 1) / 2 cresce quadraticamente, temos, N - soma = i * d . Portanto, para que exista uma solução, o número de inteiros deve dividir igualmente a quantidade N - soma. Abaixo estão as etapas:
- Itere a partir do índice (digamos i ) de 2.
- Encontre a soma dos primeiros i números (diga soma ).
- Para qualquer iteração, se (N - soma) for divisível por i, imprima esse valor de i .
- Para qualquer iteração, se N exceder a soma, imprima “-1” .
Abaixo está a implementação da abordagem acima:
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the K consecutive
// elements with a sum equal to N
void canBreakN(long long n)
{
// Iterate over [2, INF]
for (long long i = 2;; i++) {
// Store the sum
long long m = i * (i + 1) / 2;
// If the sum exceeds N
// then break the loop
if (m > n)
break;
long long k = n - m;
// Common difference should be
// divisible by number of terms
if (k % i)
continue;
// Print value of i & return
cout << i << endl;
return;
}
// Print "-1" if not possible
// to break N
cout << "-1";
}
// Driver Code
int main()
{
// Given N
long long N = 12;
// Function Call
canBreakN(N);
return 0;
}
// Java program for the above approach
class GFG{
// Function to find the K consecutive
// elements with a sum equal to N
public static void canBreakN(long n)
{
// Iterate over [2, INF]
for(long i = 2;; i++)
{
// Store the sum
long m = i * (i + 1) / 2;
// If the sum exceeds N
// then break the loop
if (m > n)
break;
long k = n - m;
// Common difference should be
// divisible by number of terms
if (k % i != 0)
continue;
// Print value of i & return
System.out.println(i);
return;
}
// Print "-1" if not possible
// to break N
System.out.println("-1");
}
// Driver Code
public static void main(String[] args)
{
// Given N
long N = 12;
// Function call
canBreakN(N);
}
}
// This code is contributed by jrishabh99
# Python3 program for the above approach
# Function to find the K consecutive
# elements with a sum equal to N
def canBreakN(n):
# Iterate over [2, INF]
for i in range(2, n):
# Store the sum
m = i * (i + 1) // 2
# If the sum exceeds N
# then break the loop
if (m > n):
break
k = n - m
# Common difference should be
# divisible by number of terms
if (k % i):
continue
# Print value of i & return
print(i)
return
# Print "-1" if not possible
# to break N
print("-1")
# Driver Code
# Given N
N = 12
# Function call
canBreakN(N)
# This code is contributed by code_hunt
// C# program for the above approach
using System;
class GFG{
// Function to find the K consecutive
// elements with a sum equal to N
public static void canBreakN(long n)
{
// Iterate over [2, INF]
for(long i = 2;; i++)
{
// Store the sum
long m = i * (i + 1) / 2;
// If the sum exceeds N
// then break the loop
if (m > n)
break;
long k = n - m;
// Common difference should be
// divisible by number of terms
if (k % i != 0)
continue;
// Print value of i & return
Console.Write(i);
return;
}
// Print "-1" if not possible
// to break N
Console.Write("-1");
}
// Driver Code
public static void Main(string[] args)
{
// Given N
long N = 12;
// Function call
canBreakN(N);
}
}
// This code is contributed by rock_cool
<script>
// Javascript program for the above approach
// Function to find the K consecutive
// elements with a sum equal to N
function canBreakN(n)
{
// Iterate over [2, INF]
for(let i = 2;; i++)
{
// Store the sum
let m = parseInt(i * (i + 1) / 2, 10);
// If the sum exceeds N
// then break the loop
if (m > n)
break;
let k = n - m;
// Common difference should be
// divisible by number of terms
if (k % i != 0)
continue;
// Print value of i & return
document.write(i);
return;
}
// Print "-1" if not possible
// to break N
document.write("-1");
}
// Given N
let N = 12;
// Function call
canBreakN(N);
// This code is contributed by sureh07.
</script>
3
Complexidade de tempo: O (K), onde K é o número do elemento cuja soma é K.
Espaço auxiliar: O (1)
Aprendendo inglês e usando o Anki? Use o Faluchu e esqueça os cartões. É gratis!
Usar o Faluchu