blob: bf67830c7fa6fa4f90a71e96f10262ee33fbaa4c (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
/*
Week 136:
https://theweeklychallenge.org/blog/perl-weekly-challenge-136
Task #2: Fibonacci Sequence
You are given a positive number $n.
Write a script to find how many different sequences you can create using Fibonacci numbers where the sum of unique numbers in each sequence are the same as the given number.
*/
import java.util.ArrayList;
import java.util.List;
public class FibonacciSequence {
public static void main(String[] args) {
System.out.println("Example 1: " + getFibonacciSequence(16));
System.out.println("Example 2: " + getFibonacciSequence(9));
System.out.println("Example 3: " + getFibonacciSequence(15));
}
public static int getFibonacciSequence(int sum) {
List<Integer> fibonacci = getFibonacciSeriesUpto(sum);
List<List<Integer>> combinations = getUniqueCombinations(fibonacci);
int count = 0;
for (List<Integer> c:combinations) {
if (sumList(c) == sum) {
count++;
}
}
return count;
}
public static List<Integer> getFibonacciSeriesUpto(int sum) {
List<Integer> fibonacci = new ArrayList<>();
fibonacci.add(1);
fibonacci.add(2);
int size = 2;
while (fibonacci.get(size - 1) + fibonacci.get(size - 2) <= sum) {
fibonacci.add(fibonacci.get(size - 1) + fibonacci.get(size - 2));
size++;
}
return fibonacci;
}
public static int sumList(List<Integer> list) {
int sum = 0;
for (int i: list) {
sum += i;
}
return sum;
}
// stackoverflow
//
// https://stackoverflow.com/questions/5162254/all-possible-combinations-of-an-array
public static List<List<Integer>> getUniqueCombinations(List<Integer> elements) {
List<List<Integer>> combinationList = new ArrayList<List<Integer>>();
for ( long i = 1; i < Math.pow(2, elements.size()); i++ ) {
List<Integer> list = new ArrayList<Integer>();
for ( int j = 0; j < elements.size(); j++ ) {
if ( (i & (long) Math.pow(2, j)) > 0 ) {
list.add(elements.get(j));
}
}
combinationList.add(list);
}
return combinationList;
}
}
|
