Given an integer N, our task is to check if N can be divided into K consecutive elements with a sum equal to N. Print -1 if it is not possible to divide in this manner, otherwise print the value K.
Examples:
Input: N = 12
Output: 3
Explanation:
The integer N = 12 can be divided into 3 consecutive elements {3, 4, 5} where 3 + 4 + 5 = 12.
Input: N = 8
Output: -1
Explanation:
No such division of integer 8 is possible.
Approach: To solve the problem mentioned above let us divide the integer N into i consecutive numbers. The terms of the sequence will look like (d+1), (d+2), (d+3)…..(d+i) where d is the common difference present in each of the integers and the sum of this sequence should be equal to N.
So, the sum of these number can also be expressed as:
As the sum = i * (i + 1) / 2 grows quadratically, we have, N – sum = i * d. Hence, for a solution to exist, the number of integers should evenly divide the quantity N – sum. Below are the steps:
- Iterate from index(say i) from 2.
- Find the sum of first i numbers(say sum).
- For any iteration if (N – sum) is divisible by i then print that value of i.
- For any iteration if N exceeds the sum then print “-1”.
Below is the implementation of the above approach:
C++
// 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 Nvoid 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 Codeint main(){ // Given N long long N = 12; // Function Call canBreakN(N); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to find the K consecutive// elements with a sum equal to Npublic 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 Codepublic static void main(String[] args){ // Given N long N = 12; // Function call canBreakN(N);}}// This code is contributed by jrishabh99 |
Python3
# Python3 program for the above approach# Function to find the K consecutive# elements with a sum equal to Ndef 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 NN = 12# Function callcanBreakN(N)# This code is contributed by code_hunt |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the K consecutive// elements with a sum equal to Npublic 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 Codepublic static void Main(string[] args){ // Given N long N = 12; // Function call canBreakN(N);}} // This code is contributed by rock_cool |
Javascript
<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
Time Complexity: O(K), where K is the number of element whose sum is K.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
