Ad

Given an integer num, return an array consisting of positive consecutive integers that sum to num. There may be multiple sequences that work; return the sequence with the largest number of consecutive integers. Return an empty array if there are no solutions of at least 2 consecutive integers.

Example:

maxConsecutiveSum(45) returns [1,2,3,4,5,6,7,8,9].

Notice that [14,15,16] also add to 45 but there is a solution that has more numbers in it.

Code
Diff
  • public class MaxConsecutiveSum {
      
      public static class ConsecutiveInts {
        public final int start;
        public final int numElements;
        
        public ConsecutiveInts(int start, int numElements) {
          this.start = start;
          this.numElements = numElements;
        }
        
        public int[] asIntArray() {
          int[] result = new int[numElements];
          for (int i = 0; i < numElements; i++) {
            result[i] = start + i;
          }
          return result;
        }
      }
      public static ConsecutiveInts maxConsecutiveSumHelper(int num){
        // Can only use positive integers, so anything less than 1 won't work.
        if (num < 1) {
          return new ConsecutiveInts(0, 0);
        }
        int start = 1; //  current lowest possible number in the consecutive integers
        long sum = 0; // Use a long to avoid overflow.
        // Largest possible sum of at least 2 consecutive would be (num/2) + (num/2 + 1).
        final int highestPossible = Math.min(num, (num / 2) + 2);
        for (int i = 1; i < highestPossible; i++) {
          sum += i;
          // If our sum exceeds the target, start chopping off the smallest numbers.
          while (sum > num) {
            sum -= start;
            start++;
          }
          if (sum == num) {
            return new ConsecutiveInts(start, i - start + 1);
          }
          // else, sum < num, so keep going.
        }
        // No two consecutive integers below num.
        return new ConsecutiveInts(0, 0);
      }
      
      public static int[] maxConsecutiveSum(int num){
        return maxConsecutiveSumHelper(num).asIntArray();
      }
    }
    
    • public class MaxConsecutiveSum{
    • public class MaxConsecutiveSum {
    • public static class ConsecutiveInts {
    • public final int start;
    • public final int numElements;
    • public ConsecutiveInts(int start, int numElements) {
    • this.start = start;
    • this.numElements = numElements;
    • }
    • public int[] asIntArray() {
    • int[] result = new int[numElements];
    • for (int i = 0; i < numElements; i++) {
    • result[i] = start + i;
    • }
    • return result;
    • }
    • }
    • public static ConsecutiveInts maxConsecutiveSumHelper(int num){
    • // Can only use positive integers, so anything less than 1 won't work.
    • if (num < 1) {
    • return new ConsecutiveInts(0, 0);
    • }
    • int start = 1; // current lowest possible number in the consecutive integers
    • long sum = 0; // Use a long to avoid overflow.
    • // Largest possible sum of at least 2 consecutive would be (num/2) + (num/2 + 1).
    • final int highestPossible = Math.min(num, (num / 2) + 2);
    • for (int i = 1; i < highestPossible; i++) {
    • sum += i;
    • // If our sum exceeds the target, start chopping off the smallest numbers.
    • while (sum > num) {
    • sum -= start;
    • start++;
    • }
    • if (sum == num) {
    • return new ConsecutiveInts(start, i - start + 1);
    • }
    • // else, sum < num, so keep going.
    • }
    • // No two consecutive integers below num.
    • return new ConsecutiveInts(0, 0);
    • }
    • public static int[] maxConsecutiveSum(int num){
    • return new int[0];
    • return maxConsecutiveSumHelper(num).asIntArray();
    • }