2
\$\begingroup\$

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 (\$\le 10^7\$) 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++;
            }
        }
    }

}
\$\endgroup\$
  • \$\begingroup\$ Hint based on @RE60K's answer: can you factor j*(j+1)/2 - i*(i+1)/2? What does this say about the number of possible solutions? \$\endgroup\$ – jschnei Jun 16 '17 at 7:13
1
\$\begingroup\$

Some ideas that can improve the complexity:

  • I am seeing that you are trying to equate num to i + (i+1) + ... + j, you can calculate this by j*(j+1)/2 - i*(i-1)/2

  • Further for a given i if we assume that num = j*(j+1)/2 - i*(i+1)/2 we can solve the quadratic equation and check if we get integral roots, that makes the whole solution O(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 = num is 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;
    }

}
\$\endgroup\$
  • \$\begingroup\$ actually i am not getting your what you are suggesting. it would be really great if you could ellaborate a bit more. thanks. :) \$\endgroup\$ – kumarmo2 Jun 10 '17 at 13:58
1
\$\begingroup\$

(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));
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.