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.
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();
- }
import static org.junit.jupiter.api.Assertions.assertArrayEquals; import java.util.Arrays; import org.junit.jupiter.api.Test; class MaxConsecutiveSumTest { @Test public void testMaxConsecutiveSum() { testHelper(new int[] {}, -1); testHelper(new int[] {}, 0); testHelper(new int[] {}, 1); testHelper(new int[] {}, 2); testHelper(new int[] {1, 2}, 3); testHelper(new int[] {2, 3}, 5); testHelper(new int[] {2, 3, 4, 5, 6, 7, 8, 9}, 44); testHelper(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9}, 45); testHelper(new int[] {9, 10, 11, 12, 13, 14, 15, 16}, 100); testHelper(new int[] {8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}, 182); testHelper(new int[] {495, 496}, 991); testHelper(new int[] {}, 1024); testHelper(new int[] {1530868, 1530869, 1530870, 1530871}, 6123478); testHelper(new int[] {}, 1073741824); // 2^30 testHelper(new int[] {1073741823, 1073741824}, Integer.MAX_VALUE); // 2^31 - 1 } public void testHelper(int[] expected, int inputNum) { int[] actual = MaxConsecutiveSum.maxConsecutiveSum(inputNum); assertArrayEquals(expected, actual, () -> "maxConsecutiveSum(" + inputNum + ") returned " + Arrays.toString(actual) + ", expected " + Arrays.toString(expected)); } }
import org.junit.Test;import static org.junit.Assert.assertArrayEquals;import org.junit.runners.JUnit4;- import static org.junit.jupiter.api.Assertions.assertArrayEquals;
public class SolutionTest {@Testpublic void testSomething() {assertArrayEquals(MaxConsecutiveSum.maxConsecutiveSum(45),new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9});assertArrayEquals(MaxConsecutiveSum.maxConsecutiveSum(3),new int[]{1, 2});assertArrayEquals(MaxConsecutiveSum.maxConsecutiveSum(2),new int[0]);assertArrayEquals(MaxConsecutiveSum.maxConsecutiveSum(182),new int[]{44, 45, 46, 47});}- import java.util.Arrays;
- import org.junit.jupiter.api.Test;
- class MaxConsecutiveSumTest {
- @Test
- public void testMaxConsecutiveSum() {
- testHelper(new int[] {}, -1);
- testHelper(new int[] {}, 0);
- testHelper(new int[] {}, 1);
- testHelper(new int[] {}, 2);
- testHelper(new int[] {1, 2}, 3);
- testHelper(new int[] {2, 3}, 5);
- testHelper(new int[] {2, 3, 4, 5, 6, 7, 8, 9}, 44);
- testHelper(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9}, 45);
- testHelper(new int[] {9, 10, 11, 12, 13, 14, 15, 16}, 100);
- testHelper(new int[] {8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}, 182);
- testHelper(new int[] {495, 496}, 991);
- testHelper(new int[] {}, 1024);
- testHelper(new int[] {1530868, 1530869, 1530870, 1530871}, 6123478);
- testHelper(new int[] {}, 1073741824); // 2^30
- testHelper(new int[] {1073741823, 1073741824}, Integer.MAX_VALUE); // 2^31 - 1
- }
- public void testHelper(int[] expected, int inputNum) {
- int[] actual = MaxConsecutiveSum.maxConsecutiveSum(inputNum);
- assertArrayEquals(expected, actual,
- () -> "maxConsecutiveSum(" + inputNum + ") returned " + Arrays.toString(actual)
- + ", expected " + Arrays.toString(expected));
- }
- }