CareerCup

Instead of checking all numbers in the given range, we can actually generate all numbers.
Note that if we fix A, the other digits must follow the fibonacci rule.

This will be much faster than checking all the numbers in the range. It takes 0.006s to print all fibonacci numbers between 1 and 1,000,000,000

#include <stdio.h>
#include <math.h>

int NumDigits(long long num) {
    int nd = 0;
    do {
        nd++, num /= 10;
    } while (num);
    return nd;
}
long long AppendNumber(long long cur, int num) { // Append num to the end of cur
    return cur * pow(10, NumDigits(num)) + num;
}
void PrintFibInRange(int from, int to) {
    for (int a = 1; ; a++) {
        long long n = AppendNumber(AppendNumber(a, a), a+a); // number "a a a+a"
        if (n > to)
            return;
        int prev1 = a+a, prev2 = a, tmp;
        while (n <= to) {   // generate the remaining numbers
            if (n >= from)  // using the fibonacci rule
                printf("%lld\n", n);
            tmp = prev1+prev2;
            prev2 = prev1;
            prev1 = tmp;
            n = AppendNumber(n, tmp);
        }
    }
}
int main() {
    PrintFibInRange(1, 1000000000);
    return 0;
}

From what I understand from the input in the digit representation of a number X if we can decompose to

X = A A1 A2 .. AN
with Ai = Ai-1 + Ai-2 then X is Fibonacci number

Some other observation to reduce the complexity
- A = A1 (as show on all of your example)
- Ai > Aj if i > j that means the number of digit represent Ai > number of digit represent Aj
- N is at least 2 (or there're at least 3 numbers)

My solution is a function to detect if a number is fibonacci number.

bool isFibonacci(long long val) {
    string s = to_string(val);
    int digits = s.length();
    int max_length = digits / 3; // as we need at least 3 number
	
    for (l = 1; l <= max_length; ++l) 
        if (isFibonacci_helper(s, l)) 
          return true;	// stop if we find feasible solution 
    return false;
}

bool isFibonacci_helper(const string& s, int start_length){
    int p = 0;
    string sA  = s.substr(p, start_length); p+= start_length;
    string sA1 = s.substr(p, start_length); p+= start_length;
    if (sA.compare(sA1) != 0) // check the condition that A1 = A
        return false; 
    long long A = stoi(sA);
    long long A1= A;
    long long A2 = A + A1;
    while (p < s.length()) {
        string sA2 = to_string(A2);
        if (p + sA2.length() > s.length())
             return false;
        string sA2c = s.sub_str(p, sA2.length());
        if (sA2.compare(sA2c) != 0) // check the condition that A2 = A + A1 
            return false; 	
        p += sA2.length();
        A = A1; A1 = A2; A2 = A + A1;
    }
    return true;
}

Pretty elegant solution using generators in C#:

static IEnumerable<long> Fibonacci(long a, long b)
{
    long c;
    yield return a;
    yield return b;
    while (true)
    {
        yield return c = a + b;
        a = b;
        b = c;
    }
}

static IEnumerable<long> FibonacciRange(long a, long b, long from, long to)
{
    return Fibonacci(a, b).SkipWhile(x => x < from).TakeWhile(x => x <= to);
}

If I'm understanding this correctly, this should be fairly straightforward. Here's an iterative solution (in C#):

public static void PrintFibonacci(int start, int end)
		{
			int previousFib = 0, currentFib = start;
			while (currentFib < end)
			{
				Console.WriteLine(currentFib);
				int newFib = previousFib + currentFib;
				previousFib = currentFib;
				currentFib = newFib;
			}
		}