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.
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++
// 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 Gvoid 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 Codeint main(){ int G = 125; findValuesOfK(G); return 0;} |
Java
// Java program for the above approachimport 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 |
Python3
# Python 3 program for the above approachfrom math import sqrt# Function to find the count the value# of K such that sum of the first N# numbers from K is Gdef 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 Codeif __name__ == '__main__': G = 125 findValuesOfK(G) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;class GFG{// Function to find the count the value// of K such that sum of the first N// numbers from K is Gstatic 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 codepublic static void Main(){ int G = 125; findValuesOfK(G);}}// This code is contributed by sanjoy_62 |
Javascript
<script>// 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 document.write(count); } // Driver code var G = 125; findValuesOfK(G);// This code is contributed by shivanisinghss2110</script> |
Output:
4
Time Complexity: O(?G)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
