मान लीजिए हमारे पास एक धनात्मक पूर्णांक N है, हमें ढूंढना है कि इसे लगातार धनात्मक पूर्णांकों के योग के रूप में कितने अलग-अलग तरीकों से लिखा जा सकता है?
उदाहरण के लिए, यदि इनपुट 10 है, तो आउटपुट 3 होगा (नोट: मूल उदाहरण में त्रुटि है, सही उत्तर 3 है: 10, 1+2+3+4, 5+5 नहीं क्योंकि लगातार होना चाहिए)।
हल करने का दृष्टिकोण
गणितीय अंतर्दृष्टि: N = k*a + k*(k-1)/2 जहां k पदों की संख्या है और a पहला पद है।
ret = 1 से शुरू करें (N स्वयं)
k = 2 से शुरू करते हुए, जब तक k*(k+1)/2 <= N
जांचें कि क्या (N - k*(k+1)/2) k से विभाज्य है
यदि हां, तो एक वैध अनुक्रम मौजूद है
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int consecutiveNumbersSum(int N) {
int ret = 1;
for(int i = 2; ; i++){
int sum = (i * (i + 1)) / 2;
if(sum > N) break;
int rem = N - sum;
ret += (rem % i == 0);
}
return ret;
}
};
int main(){
Solution ob;
cout << (ob.consecutiveNumbersSum(10));
return 0;
}
इनपुट
10
आउटपुट
2
