Given a number n, find the number of ways to represent this number as a sum of 2 or more consecutive natural numbers. Examples :
Input : n = 15 Output : 3 15 can be represented as: 1 + 2 + 3 + 4 + 5 4 + 5 + 6 7 + 8 Input :10 Output :2 10 can only be represented as: 1 + 2 + 3 + 4
We have already discussed one approach in below post. Count ways to express a number as sum of consecutive numbers Here a new approach is discussed. Suppose that we are talking about the sum of numbers from X to Y ie [X, X+1, …, Y-1, Y] Then the arithmetic sum is
(Y+X)(Y-X+1)/2
If this should be N, then
2N = (Y+X)(Y-X+1)
Note that one of the factors should be even and the other should be odd because Y-X+1 and Y+X should have opposite parity because Y-X and Y+X have the same parity. Since 2N is anyways even, we find the number of odd factors of N. For example, n = 15 all odd factors of 15 are 1 3 and 5 so the answer is 3.
C++
// C++ program to count number of ways to express// N as sum of consecutive numbers.#include <bits/stdc++.h>using namespace std;// returns the number of odd factorsint countOddFactors(long long n){ int odd_factors = 0; for (int i = 1; 1ll * i * i <= n; i++) { if (n % i == 0) { // If i is an odd factor and // n is a perfect square if (1ll * i * i == n) { if (i & 1) odd_factors++; } // If n is not perfect square else { if (i & 1) odd_factors++; int factor = n / i; if (factor & 1) odd_factors++; } } } return odd_factors - 1;}// Driver Codeint main(){ // N as sum of consecutive numbers long long int N = 15; cout << countOddFactors(N) << endl; N = 10; cout << countOddFactors(N) << endl; return 0;} |
Java
// Java program to count number // of ways to express N as sum // of consecutive numbers.import java.io.*;class GFG{// returns the number// of odd factorsstatic int countOddFactors(long n){ int odd_factors = 0; for (int i = 1; 1 * i * i <= n; i++) { if (n % i == 0) { // If i is an odd factor and // n is a perfect square if (1 * i * i == n) { if ((i & 1) == 1) odd_factors++; } // If n is not // perfect square else { if ((i & 1) == 1) odd_factors++; int factor = (int)n / i; if ((factor & 1) == 1) odd_factors++; } } } return odd_factors - 1;}// Driver Codepublic static void main(String args[]){ // N as sum of consecutive numbers long N = 15; System.out.println(countOddFactors(N)); N = 10; System.out.println(countOddFactors(N));}}// This code is contributed by // Manish Shaw(manishshaw1) |
Python3
# Python3 program to count number # of ways to express N as sum# of consecutive numbers. # returns the number# of odd factorsdef countOddFactors(n) : odd_factors = 0 i = 1 while((1 * i * i) <= n) : if (n % i == 0) : # If i is an odd factor and # n is a perfect square if (1 * i * i == n) : if (i & 1) : odd_factors = odd_factors + 1 # If n is not perfect square else : if ((i & 1)) : odd_factors = odd_factors + 1 factor = int(n / i) if (factor & 1) : odd_factors = odd_factors + 1 i = i + 1 return odd_factors - 1 # Driver Code # N as sum of consecutive numbersN = 15print (countOddFactors(N)) N = 10print (countOddFactors(N)) # This code is contributed by # Manish Shaw(manishshaw1) |
C#
// C# program to count number of // ways to express N as sum of // consecutive numbers.using System;class GFG{ // returns the number // of odd factors static int countOddFactors(long n) { int odd_factors = 0; for (int i = 1; 1 * i * i <= n; i++) { if (n % i == 0) { // If i is an odd factor and // n is a perfect square if (1 * i * i == n) { if ((i & 1) == 1) odd_factors++; } // If n is not // perfect square else { if ((i & 1) == 1) odd_factors++; int factor = (int)n / i; if ((factor & 1) == 1) odd_factors++; } } } return odd_factors - 1; } // Driver Code static void Main() { // N as sum of consecutive numbers long N = 15; Console.WriteLine(countOddFactors(N)); N = 10; Console.WriteLine(countOddFactors(N)); }} |
PHP
<?php// PHP program to count number // of ways to express N as sum// of consecutive numbers.// returns the number// of odd factorsfunction countOddFactors($n){ $odd_factors = 0; for ($i = 1; 1 * $i * $i <= $n; $i++) { if ($n % $i == 0) { // If i is an odd factor and // n is a perfect square if (1 * $i * $i == $n) { if ($i & 1) $odd_factors++; } // If n is not perfect square else { if ($i & 1) $odd_factors++; $factor = $n / $i; if ($factor & 1) $odd_factors++; } } } return $odd_factors - 1;}// Driver Code// N as sum of consecutive numbers$N = 15;echo (countOddFactors($N) . ("\n"));$N = 10;echo (countOddFactors($N));// This code is contributed by // Manish Shaw(manishshaw1)?> |
Javascript
<script>// JavaScript program to count number of ways to express// N as sum of consecutive numbers.// returns the number of odd factorsfunction countOddFactors(n){ let odd_factors = 0; for (let i = 1; 1 * i * i <= n; i++) { if (n % i == 0) { // If i is an odd factor and // n is a perfect square if (1 * i * i == n) { if (i & 1) odd_factors++; } // If n is not perfect square else { if (i & 1) odd_factors++; let factor = n / i; if (factor & 1) odd_factors++; } } } return odd_factors - 1;}// Driver Code// N as sum of consecutive numberslet N = 15;document.write(countOddFactors(N),"</br>");N = 10;document.write(countOddFactors(N),"</br>");// This code is contributed by shinjanpatra</script> |
Output :
3 1
The Time complexity for this program is O(N^0.5).
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!
