java - Number of consectuive sums error?

Question

I am working on a program that takes an integer and finds the number of combinations of consecutive sums that the integer has:

The number 13 can be expressed as a sum of consecutive positive integers 6 + 7. Fourteen can be expressed as 2 + 3 + 4 + 5, also a sum of consecutive positive integers. Some numbers can be expressed as a sum of consecutive positive integers in more than one way. For example, 25 is 12 + 13 and is also 3 + 4 + 5 + 6 + 7.

I researched and read that it's the number of odd factors minus one. So I wrote a program that finds the number of odd factors and my answer is still wrong in certain cases. Any insight?

Code seems to work fine but there is a crash due to Timeout which is probably due to optimization error.

The constraints for possible input size is 1 to 10^(12)

The code below is copied from alfasin's answer below:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;


  static long consecutive(long num) {
    while (num % 2 == 0) num /= 2;
    return  consecutiveHelper(num);
}

public static long consecutiveHelper(long num) {
    return LongStream.rangeClosed(3, (num / 2)).parallel().filter(x -> x % 2 != 0).map(fn -> (num % fn == 0) ? 1 : 0).sum();
}
        public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        final String fileName = System.getenv("OUTPUT_PATH");
        BufferedWriter bw = null;
        if (fileName != null) {
            bw = new BufferedWriter(new FileWriter(fileName));
        }
        else {
            bw = new BufferedWriter(new OutputStreamWriter(System.out));
        }

        int res;
        long num;
        num = Long.parseLong(in.nextLine().trim());

        res = consecutive(num);
        bw.write(String.valueOf(res));
        bw.newLine();

        bw.close();
    }
}

This is what i currently have

Answer 1

As the post i answered to was duplicate, I copied my answer here as well.

Let's try to find a pseudo-optimized method to resolve your problem :

What you need to do is to decompose your number in prime factors.

For example, if you take 1200 :

1200 = 2*2*2*2*3*5*5 = 1 * 2^4 * 3^1 * 5^2

You can then analyze how you could get odd factors with those prime factors. A quick analyze will tell you that :

• odd * odd = odd
• odd * even = even
• even * even = even

With that in mind, let's find all the factors we get with odd * odd :

• 1 * 1 = 1
• 3 * 1 = 3
• 5 * 1 = 5
• 5 * 3 = 15
• 5 * 5 = 25
• 5 * 5 * 3 = 75

A quick way to find these combinations without writing them all is the "plus 1 method" : add 1 to the number of occurences of each prime odd factor, and multiply them together :

We found that 1200 = 1 * 2^4 * 3^1 * 5^2, so we can do :

• ("number of 3" + 1) ("number of 5" + 1) = (1 + 1) ( 2 + 1) = 6

There are 6 odd factors for the number 1200, and as you stated, remove 1 from that number to get the number of combinations of consecutive sums that 1200 has :

• 6 - 1 = 5 <-- woohoo ! finally got the result !

---

Now, let's look at the code. What we want to have is a Map, the keys being the prime factors and the values being the number of their occurences :

/*
    If number is odd,
    find the number in the keys and add 1 to its value.
    If the number is not in the keys, add it with value = 1.
 */
public static void addValue(Map<Integer, Integer> factors, int i) {
    if(i % 2 != 0) {
        int count = factors.containsKey(i) ? factors.get(i) : 0;
        factors.put(i, ++count);
    }
}

/*
    Classic algorithm to find prime numbers
 */
public static Map<Integer, Integer> oddPrimeFactors(int number) {
    int n = number;
    Map<Integer, Integer> factors = new HashMap<>();
    for (int i = 2; i <= n / i; i++) {
        while (n % i == 0) {
            addValue(factors, i);
            n /= i;
        }
    }

    if(n > 1) addValue(factors, n);
    return factors;
}

With that, let's try to print what the map contains for number 1200 :

public static void main(String[] args) {
    int n = 1200;

    System.out.println(oddPrimeFactors(n));
}

$n : {3=1, 5=2}

Good ! Now let's finish the program with the method we developed before :

public static int combinations = 1;

public static void main(String[] args) {
    int n = 1200;

    oddPrimeFactors(n).forEach((key, value) -> combinations *= (value + 1));
    combinations--;

    System.out.println(combinations);
}

$combinations = 5

Finished ! feel free to ask if you did not understand something !

Note : I tried my program with the max value Integer can handle and it took less than one second for my program to proceed, which seems pretty fast to me. It could probably be faster though, it's up to you to find the most optimized version of this code !