Expressing a number as sum of consecutive | Set 2 (Using odd factors)
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 factors int 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 Code int 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 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 public 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 factors def 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 numbers N = 15 print (countOddFactors(N)) N = 10 print (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 factors function 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 factors function 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 numbers let N = 15; document.write(countOddFactors(N), "</br>" ); N = 10; document.write(countOddFactors(N), "</br>" ); // This code is contributed by shinjanpatra </script> |
3 1
The Time complexity for this program is O(N^0.5).