CareerCup

It looks like the Change-making problem.
As Fibonacci is a canonical system, a solution for spliting N in a sum of fib numbers is just to get the highest fibonacci number F and then do the same with N' = N-F ...

for N= 70 instead of getting 34+34+2, I will get 55+13+2.

here is my solution

public class FibSplitter {
	
	private List<Integer> cache = new ArrayList<Integer>();
	
	public FibSplitter() {
		cache.add(0);
		cache.add(1);
	}

	/**
	 * Returns the highest Fibonacci number lower than n.
	 * @param n
	 * @return
	 */
	private int getHighestFibNumber(int n) {
		int index = 0;
		int f1 = cache.get(index);
		int f2 = cache.get(index + 1);
		int temp;
		while (f2 <= n) {
			if (index < cache.size() - 2) {
				f1 = f2;
				f2 = cache.get(index + 2);
			} else {
				temp = f1;
				f1 = f2;
				f2 = temp + f1;
				cache.add(f2);
			}
			index++;
		}
		return f1;
	}
	
	public List<Integer> split(int n) {
		if (n == 0) return new LinkedList<Integer>();
		int f = getHighestFibNumber(n);
		List<Integer> result = split(n-f);
		result.add(f);
		return result;
	}
	
	public static void main(String[] args) {
		FibSplitter fib = new FibSplitter();
		System.out.println(fib.split(7)); // [2, 5]
		System.out.println(fib.split(70)); // [2, 13, 55]
		System.out.println(fib.split(2583)); // [2, 5, 13, 34, 89, 233, 610, 1597]
	}
	
}

Following is a DP solution in O(n) using O(n) space :-

import java.util.ArrayList;
import java.util.List;

public class fibosum {
	
	public static int minFiboSum(int n) {
		List<Integer> fiboNums = new ArrayList<Integer>();
		int a=1,b=1,c=1;
		while(true) {
			c = a+b;
			if(c<=n)
				fiboNums.add(c);
			else break;
			a = b;
			b = c;
		}
		int minSum[] = new int[n+1];
		minSum[0] = 0;
		for(int i = 1;i<=n;i++) {
			minSum[i] = n; 
			for(Integer fibo : fiboNums) {
				int k = fibo;
				int steps = 0;
				if(k<=i) {
					steps = minSum[i-k] + 1;
					minSum[i] = Math.min(minSum[i], steps);
						
				}
				else break;
			}
		}
		return minSum[n];
	}
	public static void main(String args[]) {
		System.out.println(minFiboSum(7));
		System.out.println(minFiboSum(70));
	}
}

This problem is similar to that of finding prime factors of a number, only the factors considering here are different.

The Algorithm works by Stacking up the fibonacci numbers till the number crosses given "n" value.
Pop the number from the stack and compare the "sum" + the number retrieved with "n".
If the total is greater than "n" then ignore the number retrieved, iterate for next element from the stack. If the value is lesser then add up the number to sum and continue the recursion till the "sum" became equal to "n".

import java.util.Stack;

public class HelloWorld{

static Stack st = new Stack();

     public static void main(String []args){
        fibonacciSum(123);
     }

    public static void fibonacciSum(int n){
    
    int prev = 1, cur = 2;
    st.push(prev);
    while(cur<n){
        int temp = prev;
        prev = cur;
        cur = temp + prev;
        st.push(prev);
    }
    int sum = (int)st.pop();
    System.out.println(sum);
    recSum(sum,n);
    }

    public static void recSum(int sum, int n){
       if((sum+(int)st.peek())==n){
           System.out.println(sum+(int)st.peek() + " - " + st.pop());
       }
       else if((sum+(int)st.peek())>n){
           st.pop();
           recSum(sum, n);
       }
       else if((sum+(int)st.peek())<n){
           sum+=(int)st.peek();
           System.out.println(sum + " - " + st.peek());
           recSum(sum,n);
       }
    }
}

Time complexity of this algorithm is log(sqrt(n)).

Trying to implement the same algorithm to handle with duplicates will depreciate the efficiency.

My dynamic programming solution, (in python because I dislike java):

First, define a fibonacci function with memoization so we can get the Nth fibonacci number in O(N).

fib = dict()

	def fibonacci(i):
		if not fib.get(i):
			if i < 2:
				fib[i] = 1
			else:
				fib[i] = fibonacci(i-1) + fibonacci(i-2)
	
		return fib[i]

Now we can build up the solution from 1 -> N using DP. In general for an arbitrary array of integers, if we have an array of E elements, the DP step looks like:

DP(i) = min(1 + DP(i - ej, j-1)) for 0 < j < len(E), where ej is the jth element of E.

In this algorithm, E is just the sequence of fibonacci numbers. Since fibonacci number sequence is infinite, we only really need the numbers up to N, or up to i with each step of iteration. The repetition is tricky, since we have to test all possible multiples for ej.

def min_fib(N):

fib_index = 0
DP = dict()
E = set()

DP[0] = 0

for i in range(1, N+1):
	# update the list E with all possible fib numbers that could add up to i
	while fibonacci(fib_index) <= i:
		E.add(fibonacci(fib_index))
		fib_index += 1
	
	min_option = None

	for e in E:
		multiple = e
		# since reptitions are allowed, we have to test all multiples
		while i-multiple >= 0:
			option = multiple/e + DP[i-multiple]
			if not min_option or option < min_option: 
				min_option = option
			# extra optimization step: if there are more multiples then the min_option, it is impossible to achieve a better score and we can just break here
			if min_option <= multiple/e:
				break

			multiple += e
				
	DP[i] = min_option

return DP[N]

Runtime is O(N^3) I believe. Without repetitions allowed it would be O(N^2).

repetition is allowed. first fibonacci number is 1. 1+1+1... can give you any number. so 1?

can you give me some more test cases.

Pseudo code:

_1. Generate all the Fibs that are less than or equal to the number
_2. Obtain the numbers that would be needed and count them
___1. use BST to find the largest number in the FIB that is smaller than or equal to the actual number
___2. subtract the BST result from the number
___3. if the new number is 0 return the number of times this repeated otherwise repeat at substep 1

The complexity of this approach should approximate (not sure how to make the exact logarithmic computation due not being able to convert the growth rate of Fib as compared to n so I'm replacing Log with Fib to represent a logarithmic-like Fib growth rate) O( Fib n * Log (Fib n) ) time ( it will take O( Fib n) to compute the Fib values present and O( Fib n * Log (Fib n) ) to execute the repeated BST searches) and it will take O( Fib n) memory):

public static int numFibs(int k){
	ArrayList<Integer> fibs = computeFibs(k);

	return searches(k, fibs);
}

private static ArrayList<Integer> computeFibs(k){
	ArrayList<Integer> results = new ArrayList<Integer>();
	if(k == 0){
		return results;
	}
	results.add(1);
	if(k == 1){
		return results;
	}
	results.add(1);
	int val = -1;
	while( (val = results.get(results.size() - 1) + results.get(results.size() - 2) ) <= k){
		results.add(val);
	}
	return results;
}

private static int searches(int k, int[] fibs){
	int count = 1;
	k -= fibs[fibs.length -1];
	int maxIndex = fibs.length - 2;
	while(k > 0){
		int newIndex = bst(k, fibs, maxIndex);
		k-= fibs[newIndex];
		count++;
		maxIndex = newIndex;
	}
	return count;
}

private static int bst(int k, int[] arr, int maxIndex){
	if(maxIndex == 0){
		return 0;
	}
	int lo = 0;
	int hi = arr.length -2;
	while(lo < hi){
		int mid = ( lo + hi ) >>> 1;
		if(arr[mid] > k ){
			hi = mid -1;
		}
		else	if(arr[mid+1] < k ){
			lo = mid + 1;
		}
		else{
			return mid;
		}
	}
	if(lo == maxIndex){
		return lo;
	}
	else if(arr[lo + 1] < k){
		return lo + 1;
	}
	else{
		return lo;
	}
}

WHOW, WHOW, here's the right solution:
I don't want to explain it, but you can understand that I'm calculating fibonacci sequence, till it reaches the number and then I use that array (in which I saved the fibonacci sequence) to calculate the solution for all numbers from 1 to N (by using dp).
DP[N]= Min, where Min is calculated using :for all j in fibonacci sequence such that j<N, Min= (Min,1+DP[N-j])

private static ArrayList<Integer> CalFibonacci(int N){
         int Fib0=0;
         int Fib1=1;
         ArrayList<Integer> ret=new ArrayList<>();
         ret.add(Fib0);
         if (N==Fib0) return ret;
         ret.add((Fib1));
         if(N==Fib1) return ret;
         else{
             
             int lastAdded=Fib1;
             while(lastAdded<N){
                 //size=ret.size();
                 lastAdded=ret.get(ret.size()-1)+ret.get(ret.size()-2);
                 ret.add(lastAdded);
             }
         }
                          
         return ret;
    }
    
    private static int solveMinFibSum(int N){
        
        ArrayList<Integer> fib=CalFibonacci(N);
        //return if its in the fib series
        if(fib.get(fib.size()-1)==N){ return 1;}
        
        int[] dp=new int[N];
        int[] sol=new int[N];
        dp[0]=1;
        sol[0]=-1;
        for (int i=1;i<N;i++){
           //dp[i] stores the answer for number i+1
            int pos=PosByBinarySearch(fib,i+1);
            if(fib.get(pos)==(i+1)){
                dp[i]=1;
                sol[i]=-1;
            }
            else{
                int min=Integer.MAX_VALUE;
                int beforeMin=min;
                for(int j=pos;j>0;j--){
                    min=Math.min(min,1+ dp[(i)-fib.get(j)]);
                    if(beforeMin!=min){
                        sol[i]=j;
                    }
                    beforeMin=min;
                }
                dp[i]=min;
            }
        }
        
        //print solution
        int k=sol[N-1];
        int curr=N;
        
        //this crap is just for printing solution and verifying my solution
        while(k>=0){
            System.out.print(fib.get(k)+" ");
            curr=curr-fib.get(k);
            k=sol[curr-1];
        }
        if (k==-1) System.out.print(curr);
        System.out.println();
          //      
        return dp[N-1];
        
        
    }
    
    private static int PosByBinarySearch(ArrayList<Integer> arr, int srch){
        return BinarySearchPos(arr,srch,0,arr.size()-1);
    }
    
    private static int BinarySearchPos(ArrayList<Integer> arr, int srch, int start , int end){
        
        if(arr.get(start)>srch) return start; //should never happen , but alas
        
        if (start==end){return start;}
        
        if (end-start==1)
            
        {  //a lot of cases should never happen here, but you gotta write them up
            if (arr.get(start)==srch) return start;
            else if(arr.get(end)==srch) return end;
            else if(arr.get(end)>srch) return start;
            else return end;
        }
        else{
            int mid=(start+end)/2;
            int midvalue=arr.get(mid);
            if(midvalue==srch) return mid;
            else if(midvalue<srch){
                return BinarySearchPos(arr,srch,mid,end);
            }
            else return BinarySearchPos(arr,srch,start,mid-1);
        }
        
    }
    
    public static void main(String [] args){
        //ArrayList<Integer> ans=CalFibonacci(134654897);
        //for(int i=0;i<ans.size();i++){System.out.print(ans.get(i)+ " ");}
        System.out.println(solveMinFibSum(110));
    }
}

int solve(int N)
{
if(N==0 || N==1)
return N;
int prev = 1,curr=2;
while(curr<=N)
{
int temp = prev;
prev= curr;
curr = temp+curr;
}
return solve(N-prev)+1;
}
int Solution::fibsum(int A) {
return solve(A);
}

How about this approach ----

Need some clean up --just wrote it :)

import java.util.ArrayList;

public class FiboSum {
public ArrayList<Integer> result = new ArrayList<Integer>();

public ArrayList<Integer> fibo(int num) {
int a = 0, b = 1, c = 0, i;
ArrayList<Integer> series = new ArrayList<Integer>();
series.add(b);
for (i = 1; i <= num; i++) {
c = a + b;
if (c <= num) {
series.add(c);
a = b;
b = c;
}

}
return series;
}

public void getMinFibo(int num) {

ArrayList<Integer> series = new ArrayList<Integer>();
series = fibo(num);

result.add(series.get(series.size() - 1));
int diff = num - series.get(series.size() - 1);
if (diff >= 1) {
getMinFibo(diff);
}
System.out.print("series= " + result);
}

public static void main(String[] args) {
FiboSum ff = new FiboSum();
ff.getMinFibo(70);
}

}

can you give me some more test cases.