Find all possible values of K such that the sum of first N numbers starting from K is G
Given a positive integer G, the task is to find the number of values of K such that the sum of the first N numbers starting from K is G i.e., (K + (K + 1) + … + (K + N – 1)) = G, where N can be any positive integer.
Examples:
Input: G = 10
Output: 2
Explanation:
Following are the possible values of K:
- K = 1 and N = 4: The sum of {1, 2, 3, 4} is 10(= G).
- K = 10 and N = 1: The sum of {10} is 10(= G).
Therefore, there are two possible values of K. Hence, print 2.
Input: G = 15
Output: 2
Naive Approach: The simplest approach to solve the given problem is to check for each and every value of K from 1 to G and if the given condition is satisfied, then count this value of K. After checking for all possible values of K print the total count.
#include <iostream>
using namespace std;
// Function to count the number of values of K
int countValuesOfK(int G)
{
int count = 0;
for (int K = 1; K <= G; ++K) {
int sum = 0;
int N = 1;
// Check for each N starting from 1 until the sum
// exceeds G
while (sum < G) {
sum += K + N - 1;
if (sum == G) {
count++;
}
N++;
}
}
return count;
}
int main()
{
int G2 = 125;
cout << "Number of values of K for G = 125: "
<< countValuesOfK(G2) << endl;
return 0;
}
public class Main {
// Function to count the number of values of K
public static int countValuesOfK(int G)
{
int count = 0;
for (int K = 1; K <= G; ++K) {
int sum = 0;
int N = 1;
// Check for each N starting from 1 until the
// sum exceeds G
while (sum < G) {
sum += K + N - 1;
if (sum == G) {
count++;
}
N++;
}
}
return count;
}
public static void main(String[] args)
{
int G2 = 125;
System.out.println(
"Number of values of K for G = 125: "
+ countValuesOfK(G2));
}
}
def count_values_of_k(G):
count = 0
for K in range(1, G + 1):
sum_val = 0
N = 1
# Check for each N starting from 1 until the
# sum exceeds G
while sum_val < G:
sum_val += K + N - 1
if sum_val == G:
count += 1
N += 1
return count
if __name__ == "__main__":
G2 = 125
print("Number of values of K for G = 125:", count_values_of_k(G2))
function countValuesOfK(G) {
let count = 0;
for (let K = 1; K <= G; ++K) {
let sum = 0;
let N = 1;
// Check for each N starting from 1 until the sum exceeds G
while (sum < G) {
sum += K + N - 1;
if (sum === G) {
count++;
}
N++;
}
}
return count;
}
function main() {
const G2 = 125;
console.log("Number of values of K for G = 125: " + countValuesOfK(G2));
}
main();
Output
Number of values of K for G = 125: 4
Time Complexity: O(G2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be solved by observing the mathematical relation that for any value of 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
Therefore, the value K = G/N – (N – 1)/2. From the above relationship, it can be concluded that the possible value of K exists if and only if:
- N is the factor of G i.e., (G % N) == 0.
- N should be odd i.e., (N % 2) == 1.
Follow the steps below to solve the problem:
- Initialize the variable, say count as 0 that stores the resultant count of values of K.
- Iterate over a range [1, ?G] using the variable i and performing the following tasks:
- If g%i is equal to 0, then if i is not equal to g/i, then if i%2 is equal to 1, then add the value of count by 1 and if (g/i)%2 is equal to 1, then add the value of count by 1.
- Else, if i%2 is equal to 1, then add the value of count by 1.
- After completing the above steps, print the value of the count as the result.
Below is the implementation of the above approach.
// 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 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
# 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# 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 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
console.log(count);
}
// Driver code
var G = 125;
findValuesOfK(G);
// This code is contributed by shivanisinghss2110
Output
4
Time Complexity: O(?G)
Auxiliary Space: O(1)
Contact Us