Given an integer N, the task is to count all arithmetic progression with common difference equal to 1 and the sum of all its elements equal to N.
Examples:
Input: N = 12
Output: 3
Explanation:
Following three APs satisfy the required conditions:
- {3, 4, 5}
- {−2, −1, 0, 1, 2, 3, 4, 5}
- {−11, −10, −9, …, 10, 11, 12]}
Input: N = 963761198400
Output: 1919
Approach: The given problem can be solved using the following properties of AP:
- The sum of an AP series having N terms with first term as A and common difference 1 is given by the formula S = (N / 2 )* ( 2 *A + N − 1).
- Solving the above equation:
S = N / 2 [2 *A + N − 1].
Rearranging this and multiplying both sides by 2
=> 2 * S = N * (N + 2 * A − 1)Rearranging further
=> A = ((2 * N / i ) − i + 1) / 2.Now, iterate over all the factors of 2 * N, and check for each factor i, whether (2 * N/i) − i + 1 is even or not.
Follow the steps below to solve the problem:
- Initialize a variable, say count, to store the number of AP series possible having given conditions.
- Iterate through all the factors of 2 * N and for every ith factor, check if (2 * N / i) − i + 1 is even.
- If found to be true, increment the count.
- Print count – 1 as the required answer, as the sequence consisting only of N needs to be discarded.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count all possible// AP series with common difference// 1 and sum of elements equal to Nvoid countAPs(long long int N){ // Stores the count of AP series long long int count = 0; // Traverse through all factors of 2 * N for (long long int i = 1; i * i <= 2 * N; i++) { long long int res = 2 * N; if (res % i == 0) { // Check for the given conditions long long int op = res / i - i + 1; if (op % 2 == 0) { // Increment count count++; } if (i * i != res and (i - res / i + 1) % 2 == 0) { count++; } } } // Print count - 1 cout << count - 1 << "\n";}// Driver Codeint main(){ // Given value of N long long int N = 963761198400; // Function call to count // required number of AP series countAPs(N);} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Function to count all possible // AP series with common difference // 1 and sum of elements equal to N static void countAPs(long N) { // Stores the count of AP series long count = 0; // Traverse through all factors of 2 * N for (long i = 1; i * i <= 2 * N; i++) { long res = 2 * N; if (res % i == 0) { // Check for the given conditions long op = res / i - i + 1; if (op % 2 == 0) { // Increment count count++; } if (i * i != res && (i - res / i + 1) % 2 == 0) { count++; } } } // Print count - 1 System.out.println(count - 1); } // Driver code public static void main(String[] args) { // Given value of N long N = 963761198400L; // Function call to count // required number of AP series countAPs(N); }}// This code is contributed by Kingash. |
Python3
# Python3 program to implement# the above approach# Function to count all possible# AP series with common difference# 1 and sum of elements equal to Ndef countAPs(N) : # Stores the count of AP series count = 0 # Traverse through all factors of 2 * N i = 1 while(i * i <= 2 * N) : res = 2 * N if (res % i == 0) : # Check for the given conditions op = res / i - i + 1 if (op % 2 == 0) : # Increment count count += 1 if (i * i != res and (i - res / i + 1) % 2 == 0) : count += 1 i += 1 # Print count - 1 print(count - 1)# Driver Code# Given value of NN = 963761198400# Function call to count# required number of AP seriescountAPs(N)# This code is contributed by sanjoy_62. |
C#
// C# program for above approachusing System;public class GFG { // Function to count all possible // AP series with common difference // 1 and sum of elements equal to N static void countAPs(long N) { // Stores the count of AP series long count = 0; // Traverse through all factors of 2 * N for (long i = 1; i * i <= 2 * N; i++) { long res = 2 * N; if (res % i == 0) { // Check for the given conditions long op = res / i - i + 1; if (op % 2 == 0) { // Increment count count++; } if (i * i != res && (i - res / i + 1) % 2 == 0) { count++; } } } // Print count - 1 Console.WriteLine(count - 1); } // Driver code public static void Main(String[] args) { // Given value of N long N = 963761198400L; // Function call to count // required number of AP series countAPs(N); }}// This code is contributed by sanjoy_62. |
Javascript
<script>// Javascript program for the above approach // Function to count all possible // AP series with common difference // 1 and sum of elements equal to N function countAPs(N) { // Stores the count of AP series let count = 0; // Traverse through all factors of 2 * N for (let i = 1; i * i <= 2 * N; i++) { let res = 2 * N; if (res % i == 0) { // Check for the given conditions let op = res / i - i + 1; if (op % 2 == 0) { // Increment count count++; } if (i * i != res && (i - res / i + 1) % 2 == 0) { count++; } } } // Print count - 1 document.write(count - 1); }// Driver code // Given value of N let N = 963761198400; // Function call to count // required number of AP series countAPs(N); </script> |
Output:
1919
Time Complexity: O(√N)
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!