HackerRank‐Recursion and Backtracking - a920604a/leetcode GitHub Wiki

---

title: Recursion and Backtracking categories: - interview-preparation-kit - HackerRank comments: false

Recursion: Fibonacci Numbers

int fibonacci(int n) {
    // Complete the function.
    if(n<2) return n;
    int a = 0, b = 1, c;
    for(int i=2;i<=n ;++i){
        c = a+b;
        a=b;
        b=c;
    }
    return c;
}

Recursion: Davis' Staircase

int stepPerms(int n) {
    //  0   1   2   3   4   5   6   7
    //  1   1   2   4   7   13  24  44
    if(n<2) return 1;
    if(n==2) return 2;
    int a = 1, b=1,c=2,d;
    for(int i=3; i<=n;++i){
        d = a+b+c;
        a=b;
        b=c;
        c=d;
    }
    return d;
}

Recursive Digit Sum

int super_digit(int n){
    while(n>=10){
        int cur = 0;
        while(n){
            cur+=n%10;
            n/=10;
        }
        n=cur;
    }
    
    return n;
 }

int superDigit(string n, int k) {
    int total;
    k%=9;
    int sum=0;
    for(char c:n) sum+=c-'0';
    while(k--){
        total+=sum;
    }
    return super_digit(total);
}

Crossword Puzzle