C++ Important Programs — Fibonacci, Sorting, Search

#include <iostream>
using namespace std;

// Iterative Fibonacci
void fibonacci(int n) {
    long long a = 0, b = 1;
    cout << "Fibonacci(" << n << "): ";
    for (int i = 0; i < n; i++) {
        cout << a << " ";
        long long c = a + b;
        a = b;
        b = c;
    }
    cout << endl;
}

// Recursive Fibonacci
long long fibRec(int n) {
    if (n <= 1) return n;
    return fibRec(n-1) + fibRec(n-2);
}

int main() {
    fibonacci(10);  // 0 1 1 2 3 5 8 13 21 34
    cout << "fib(10) = " << fibRec(10) << endl;  // 55
    return 0;
}

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool isPalindrome(const string &s) {
    string rev = s;
    reverse(rev.begin(), rev.end());
    return s == rev;
}

bool isNumPalindrome(int n) {
    int original = n, reversed = 0;
    while (n > 0) {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }
    return original == reversed;
}

int main() {
    cout << boolalpha;
    cout << isPalindrome("racecar") << endl;  // true
    cout << isPalindrome("hello")   << endl;  // false
    cout << isNumPalindrome(121)    << endl;  // true
    cout << isNumPalindrome(123)    << endl;  // false
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector<int> &v) {
    int n = v.size();
    for (int i = 0; i < n-1; i++) {
        bool swapped = false;
        for (int j = 0; j < n-i-1; j++) {
            if (v[j] > v[j+1]) {
                swap(v[j], v[j+1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

int binarySearch(const vector<int> &v, int target) {
    int lo = 0, hi = v.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (v[mid] == target) return mid;
        if (v[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main() {
    vector<int> v = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(v);
    for (int n : v) cout << n << " ";  // 11 12 22 25 34 64 90
    cout << endl;

    cout << "Index of 25: " << binarySearch(v, 25) << endl;  // 2
    return 0;
}

#include <iostream>
using namespace std;

// GCD using Euclidean algorithm
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// LCM using GCD
long long lcm(int a, int b) {
    return (long long)a / gcd(a, b) * b;
}

int main() {
    cout << "GCD(48, 18) = " << gcd(48, 18) << endl;  // 6
    cout << "GCD(100, 75) = " << gcd(100, 75) << endl; // 25
    cout << "LCM(4, 6) = "   << lcm(4, 6)   << endl;  // 12
    cout << "LCM(12, 18) = " << lcm(12, 18) << endl;  // 36
    return 0;
}

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string toBinary(int n) {
    if (n == 0) return "0";
    string result = "";
    bool negative = n < 0;
    if (negative) n = -n;
    while (n > 0) {
        result += (char)('0' + n % 2);
        n /= 2;
    }
    if (negative) result += '-';
    reverse(result.begin(), result.end());
    return result;
}

int fromBinary(const string &bin) {
    int result = 0;
    for (char c : bin) {
        result = result * 2 + (c - '0');
    }
    return result;
}

int main() {
    for (int i : {0, 1, 5, 10, 42, 255}) {
        cout << i << " = " << toBinary(i) << " (binary)" << endl;
    }
    cout << "1010 (binary) = " << fromBinary("1010") << endl;  // 10
    cout << "11111111 = "      << fromBinary("11111111") << endl; // 255
    return 0;
}

#include <iostream>
using namespace std;

void pyramid(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = i; j < n; j++) cout << " ";
        for (int j = 1; j <= 2*i-1; j++) cout << "*";
        cout << endl;
    }
}

void diamond(int n) {
    // Upper half
    for (int i = 1; i <= n; i++) {
        for (int j = i; j < n; j++) cout << " ";
        for (int j = 1; j <= 2*i-1; j++) cout << "*";
        cout << endl;
    }
    // Lower half
    for (int i = n-1; i >= 1; i--) {
        for (int j = n; j > i; j--) cout << " ";
        for (int j = 1; j <= 2*i-1; j++) cout << "*";
        cout << endl;
    }
}

void numberTriangle(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) cout << j << " ";
        cout << endl;
    }
}

int main() {
    cout << "--- Pyramid (n=5) ---" << endl;
    pyramid(5);

    cout << "\n--- Diamond (n=4) ---" << endl;
    diamond(4);

    cout << "\n--- Number Triangle (n=5) ---" << endl;
    numberTriangle(5);

    return 0;
}

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *next;
    Node(int d) : data(d), next(nullptr) {}
};

Node* reverse(Node *head) {
    Node *prev = nullptr, *curr = head, *next = nullptr;
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

void print(Node *head) {
    while (head) { cout << head->data << " "; head = head->next; }
    cout << endl;
}

int main() {
    // Build: 1 -> 2 -> 3 -> 4 -> 5
    Node *head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);

    cout << "Original: "; print(head);
    head = reverse(head);
    cout << "Reversed: "; print(head);
    // 5 4 3 2 1
    return 0;
}