Count of ways to generate Sequence of distinct consecutive odd integers with sum N
Given an integer N, the task is to find the total number of ways a sequence can be formed consisting of distinct consecutive odd integers that add up to N.
Examples:
Input: N = 45
Output: 3
Explanation: 3 ways to choose distinct consecutive odd numbers that add up to 45 are –
{5, 7, 9, 11, 13}, {13, 15, 17} and {45}.Input : N = 20
Output : 1
Explanation: 9 and 11 are the only consecutive odd numbers whose sum is 20
Approach: The idea to solve the problem is based on the idea of sum of first K consecutive odd integers:
- The sum of first K consecutive odd integers is K2.
- Let there be a sequence of consecutive odd integers from (y+1)th odd number to xth odd number (x > y), whose sum is N.
- Then, x2 – y2 = N or (x + y) * (x – y) = N.
- Let a and b be two divisors of N. Therefore, a * b=N.
- Hence, x + y = a & x – y = b
- Solving these two, we get x = (a + b) / 2.
- This implies, if (a + b) is even, then x and y would be integral, which means there would exist a sequence of consecutive odd integers that adds up to N.
Follow the steps mentioned below to implement the above observation:
- Iterate through all pairs of divisors, such that their product is N.
- If the sum of such a pair of divisors is even, increment the count of answer by 1.
- Return the final count at the end.
Below is the implementation of the above approach.
C++
// C++ program for above approach: #include <bits/stdc++.h> using namespace std; // Function to calculate // Number of sequence of odd integers that // Contains distinct consecutive odd integers // That add up to N. int numberOfSequences( int N) { // Initializing count variable by 0, // That stores the number of sequences int count = 0; // Iterating through all divisors of N for ( int i = 1; i * i <= N; i++) { if (N % i == 0) { // If sum of the two divisors // Is even, we increment // The count by 1 int divisor1 = i; int divisor2 = N / i; int sum = divisor1 + divisor2; if (sum % 2 == 0) { count++; } } } // Returning total count // After completing the iteration return count; } // Driver Code int main() { int N = 45; // Function call int number_of_sequences = numberOfSequences(N); cout << number_of_sequences; return 0; } |
Java
// JAVA program to check whether sum // Is equal to target value // After K operations import java.util.*; class GFG { // Function to calculate // Number of sequence of odd integers that // Contains distinct consecutive odd integers // That add up to N. static int numberOfSequences( int N) { // Initializing count variable by 0, // That stores the number of sequences int count = 0 ; // Iterating through all divisors of N for ( int i = 1 ; i * i <= N; i++) { if (N % i == 0 ) { // If sum of the two divisors // Is even, we increment // The count by 1 int divisor1 = i; int divisor2 = N / i; int sum = divisor1 + divisor2; if (sum % 2 == 0 ) { count++; } } } // Returning total count // After completing the iteration return count; } // Driver Code public static void main(String[] args) { int N = 45 ; // Function call int number_of_sequences = numberOfSequences(N); System.out.print(number_of_sequences); } } // This code is contributed by sanjoy_62. |
Python3
# Python code for the above approach import math # Function to calculate # Number of sequence of odd integers that # Contains distinct consecutive odd integers # That add up to N. def numberOfSequences(N): # Initializing count variable by 0, # That stores the number of sequences count = 0 ; # Iterating through all divisors of N for i in range ( 1 ,math.ceil(math.sqrt(N))): if (N % i = = 0 ): # If sum of the two divisors # Is even, we increment # The count by 1 divisor1 = i; divisor2 = N / / i; sum = divisor1 + divisor2; if ( sum % 2 = = 0 ): count = count + 1 # Returning total count # After completing the iteration return count; # Driver Code N = 45 ; # Function call number_of_sequences = numberOfSequences(N); print (number_of_sequences); # This code is contributed by Potta Lokesh |
C#
// C# program for above approach: using System; class GFG { // Function to calculate // Number of sequence of odd integers that // Contains distinct consecutive odd integers // That add up to N. static int numberOfSequences( int N) { // Initializing count variable by 0, // That stores the number of sequences int count = 0; // Iterating through all divisors of N for ( int i = 1; i * i <= N; i++) { if (N % i == 0) { // If sum of the two divisors // Is even, we increment // The count by 1 int divisor1 = i; int divisor2 = N / i; int sum = divisor1 + divisor2; if (sum % 2 == 0) { count++; } } } // Returning total count // After completing the iteration return count; } // Driver Code public static void Main() { int N = 45; // Function call int number_of_sequences = numberOfSequences(N); Console.Write(number_of_sequences); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program for above approach: // Function to calculate // Number of sequence of odd integers that // Contains distinct consecutive odd integers // That add up to N. const numberOfSequences = (N) => { // Initializing count variable by 0, // That stores the number of sequences let count = 0; // Iterating through all divisors of N for (let i = 1; i * i <= N; i++) { if (N % i == 0) { // If sum of the two divisors // Is even, we increment // The count by 1 let divisor1 = i; let divisor2 = parseInt(N / i); let sum = divisor1 + divisor2; if (sum % 2 == 0) { count++; } } } // Returning total count // After completing the iteration return count; } // Driver Code let N = 45; // Function call let number_of_sequences = numberOfSequences(N); document.write(number_of_sequences); // This code is contributed by rakeshsahni </script> |
Output
3
Time Complexity: O(√N)
Auxiliary Space: O(1)
Contact Us