Triangular Sum with One Extra Number
Autumn Tournament (2023)
Submission name: sum.cpp
Problem summary
Find positive integers n and p such that S = 1 + 2 + ... + n + p and 1 ≤ p ≤ n, or report that no solution exists.
Input
One integer S.
Output
n and p separated by a space, or 0 if impossible.
Constraints
0 < S < 100000000000000000.
Worked example
Original statement sample.
Input
13
Output
4 3
Solution analysis
- Write T(n)=n(n+1)/2. A solution needs T(n)<S≤T(n)+n. The next triangular number is T(n+1)=T(n)+n+1, so at most one n can work.
- Binary-search the largest n with T(n)<S. The upper bound 1000000000 is safely above all possible n, and its triangular number fits in long long. Then calculate p=S−T(n) and check 1≤p≤n.
- For S=13, the largest triangular number strictly below it is T(4)=10. The remainder 3 is in [1,4], giving 4 3. For S=10, T(3)=6 leaves 4>3, so there is no solution.
Why it works
The valid interval for each n ends one below the next triangular number. Therefore only the largest n with T(n)<S could work; checking its remainder is both necessary and sufficient.
Complexity: O(log S) time and O(1) extra space.
Watch out. Use strict T(n)<S: p cannot be zero. Use long long for the product; floating-point square roots can round near a triangular boundary.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The valid interval for each n ends one below the next triangular number. Therefore only
// the largest n with T(n)<S could work; checking its remainder is both necessary and sufficient.
#include<iostream>
using namespace std;
long long triangular(long long n){
return n*(n+1)/2;
}
int main(){
long long total;
cin>>total;
long long low=0;
long long high=1000000000;
while(low<high){
long long middle=low+(high-low+1)/2;
if(triangular(middle)<total){
low=middle;
}
else{
high=middle-1;
}
}
long long extra=total-triangular(low);
if(low>0&&extra>=1&&extra<=low){
cout<<low<<' '<<extra<<'\n';
}
else{
cout<<0<<'\n';
}
}