FibNum-CountSum-MinItems.cpp

How many minimum numbers from fibonacci series are required such that sum of numbers should be equal to a given Number N?
Note : repetition of number is allowed.

Example:

N = 4
Fibonacci numbers : 1 1 2 3 5 .... so on
here 2 + 2 = 4 
so minimum numbers will be 2 

---------------------------------------------------------------------------------------------------------------------------


int Solution::fibsum(int A) {
  
  //Generate all fib no upto A
  
  std::set<int> s;
  int a = 1;
  int b = 1;
  s.insert(1);
  while(b <= A)
  {
      int c = a + b;
      a = b;
      b = c;
      s.insert(c);
  }
  
  int count = 0;
  
  std::set<int>::reverse_iterator itr = s.rbegin();
  
  while(itr != s.rend())
  {
      if(*itr == A)
      {
          count++;
          break;
      }
      else if(A > *itr)
      {
          count++;
          A = A - *itr;
      }
      else
      {
          itr++;
      }
  }
  return count;
}