Problem
I am trying to count the number of ways an integer can be represented as sum of 2 or more consecutive positive integers. My Code is working in under 1 second for small inputs (≤107) but after that it’s taking too long. How can I lower the time complexity of the solution?
import java.io.*;
//sum needs to contain atleast 2 elements
public class IntegerRepresentedAsSumOfConsecutivePositiveIntegers
{
public static long count = 0;
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long num = Long.parseLong(br.readLine()); //Enter a number( <=10^12)
//driver(num);
func(num);
System.out.println("count = " + count);
}
public static void func(long num)
{
long temp,i,j;
long limit = (num / 2);
for(i = 1 ; i <= limit ; i++)
{
temp = num;
j = i;
while(j < temp)
{
temp = temp - j;
j++;
}
if(j == temp)
{
count++;
}
}
}
}
Solution
Some ideas that can improve the complexity:
-
I am seeing that you are trying to equate
numtoi + (i+1) + ... + j, you can calculate this byj*(j+1)/2 - i*(i-1)/2 -
Further for a given
iif we assume thatnum = j*(j+1)/2 - i*(i+1)/2we can solve the quadratic equation and check if we get integral roots, that makes the whole solutionO(n) - You may also wanna try looking up solutions to quadratic Diophantine equations, see here, after all
j*(j+1)/2 - i*(i-1)/2 = numis a quadratic diophantine equation only.
What I would probably do
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class ConsSum {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long num = Long.parseLong(br.readLine());
System.out.println("There are " + getConsSumWays(num) + " total way(s) to get " + num);
}
private static int getConsSumWays(long n) {
int count = 0;
/*
* i + (i+1) + (i+2) + ... + j = n
* => j(j+1)-i(i-1)=2n
* => let k = j(j+1) = 2n + i(i-1)
*/
for (long i = 0; i <= n / 2; i++) {
long k = 2 * n + i * (i - 1);
/*
* j^2+j-k=0 => j = [-1+sqrt(1+4k)]/2 since j>0
*/
long j = (long) ((-1 + Math.sqrt(1 + 4 * k)) / 2);
if (j * (j + 1) == k) {
System.out.println("sum [" + i + ".." + j + "] = " + n);
count++;
}
}
return count;
}
}
(Given a choice, I wouldn’t read a single shortish input using file (or stream or channel) IO – just use an argument to main.)
static void func(long num) is neither documented nor named suggestively. It doesn’t even live up to it’s name, not returning a value, but using a class data member for result communication. This prevents multiple&concurrent use – instead, return a value.
RE60K (and jschnei) showed “analysis from the sum formula”.
Alternatively, start from the sum target: to be a sum of two consecutive natural numbers, it needs to be odd. Tabulating this for several sum lengths:
# condition min
2 1 % 2 1
3 0 % 3 3
4 2 % 4 6
5 0 % 5 10
6 3 % 6 15 3, too
7 0 % 7 21
8 4 % 8 28
9 0 % 9 36 3, too
10 5 % 10 45 5, too
11 0 % 11 55
12 6 % 12 66 3, too
15 0 % 15 130 3, 5, too
using that, I get 1, 0, 2, 0, 1, 2, 1, 0, 2, 2, 1, 1, 1, 1, 4, 0, 1, 2, 1, 1, 4… ways to “consecutively sum to” n=1..21 (throwing this at OEIS yields – nothing. Going from 2 or more consecutive positive integers to 1: oeis.org/search?q=2,1,3,1,2,3,2,1,3,3,2,2,2,2,5,1,2,3,2,2,5 – in the FORMULA paragraph, you may find the generating function – and a description:)
number of odd divisors (including n), plus one if n is a triangular number (sum from 1..k for some k).
/** For a given <em>n</em>, compute the number of ways
* to sum more than one consecutive natural number yielding <em>n</em>. */
// owes to an answer by RE60K@CR
class ConsSum {
public static void main(String[] args) throws NumberFormatException {
final long
from = args.length < 1 ? 42 : Long.parseLong(args[0]),
num = args.length < 2 ? from : Long.parseLong(args[1]);
System.out.println("There are");
for (long sum = from ; sum <= num ; sum++) {
final int ways = getConsSumWays(sum);
System.out.println(ways
+ Ending.forSingular(" way", ways) + " to get " + sum);
}
}
/** @return the number of ways to sum more than one consecutive
* natural number yielding <code>n</code>. */
private static int getConsSumWays(long n) {
int count = 0;
final long triangularCandidate = (long) (Math.sqrt(8*n + 1)/2);
final boolean triangular
= n == (triangularCandidate*(triangularCandidate+1))/2;
for (long divisor = 3 ; divisor <= n/2 ; divisor += 2)
if (0 == n % divisor)
count++;
return count + ((int)n & 1) + (triangular ? 1 : 0);
}
}
// for laughs:
/** stemming helpers etc */
class Ending {
static final java.util.regex.Pattern PLURALISER
= java.util.regex.Pattern.compile(".*(?:"
+ "(?<ies>[^aeiou]y)"
+ "|(?<es>ch|s|sh|x|z)"
+ "|[aeiou][aeiou]fe?|(?<ves>..fe?)"
+ ")");
static final String[] Plural = {
"ies",
};
/** Doesn't (yet) incorporate exceptions e.g. from
* https://en.oxforddictionaries.com/spelling/plurals-of-nouns.
* @return given (a <code>String</code> ending in)
* an English noun in singular, return the plural form. */
static String forSingular(final String singular, final int n) {
if (n == 1)
return singular;
final java.util.regex.Matcher pluraliser
= PLURALISER.matcher(singular);
if (pluraliser.matches()) {
int start;
if (0 <= (start = pluraliser.start("ies")))
return singular.substring(0, start+1) + "ies";
if (0 <= (start = pluraliser.start("es")))
return singular + "es";
if (0 <= (start = pluraliser.start("ves")))
return singular.substring(0, start+2) + "ves";
}
// regular
return singular + 's';
}
public static void main(String[] args) {
for (String s: new String[] {
"man", "child", "try", "way", "knife", "chief", "bus" })
System.out.println(s + " -> " + forSingular(s, 2));
}
}