medium-level-math.cpp

// 🔢 🟡 MEDIUM MATH TOPICS (Interview Level)

// 👉 Focus: Number theory + combinatorics + logic

// 🔹 1. Prime & Sieve ⭐⭐⭐
// Sieve of Eratosthenes ⭐⭐⭐
// Prime factorization
// Smallest prime factor (SPF)
// 🔹 2. Modular Arithmetic Advanced ⭐⭐⭐
// Modular inverse
// Fermat’s Little Theorem ⭐⭐⭐
// Modular division
// nCr % MOD efficiently
// 🔹 3. Combinatorics ⭐⭐⭐
// Pascal’s Triangle
// Counting ways problems
// Inclusion-Exclusion Principle ⭐⭐⭐
// 🔹 4. GCD Based Problems
// Extended Euclidean Algorithm ⭐⭐
// Solve linear Diophantine equations
// 🔹 5. Number Properties
// Perfect numbers
// Armstrong numbers
// Trailing zeros in factorial ⭐⭐
// 🔹 6. Matrix Basics
// Matrix multiplication
// Matrix exponentiation (intro) ⭐⭐⭐

// 👉 Goal: Solve most OA + interview math problems





// 🔹 1. PRIME & SIEVE ⭐⭐⭐
// ⭐ 1.1 Sieve of Eratosthenes
// 💡 Concept

// Efficiently find all primes up to N in O(N log log N).

// 👉 Instead of checking each number, we eliminate multiples.

// 🧠 Usage
// Precompute primes (very common)
// Range queries
// Prime factorization optimization
// ⚙️ Algorithm
// Assume all numbers prime
// Start from 2
// Mark multiples as non-prime



#include<bits/stdc++.h>
using namespace std;
vector<bool> sieve(int n) {
    vector<bool> isPrime(n+1, true);
    isPrime[0] = isPrime[1] = false;

    for(int i = 2; i * i <= n; i++) {
        if(isPrime[i]) {
            for(int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime;
}
int main() {
   int n;
    cout << "Enter a number: ";
    cin>>n;
    vector<bool> primes = sieve(n);
    cout << "Primes up to " << n << ": ";
    for(int i = 2; i <= n; i++) {
        if(primes[i]) {
            cout << i << " ";
        }
    }
    return 0;
}






// ⭐ 1.2 Prime Factorization
// 💡 Concept

// Break number into product of primes
// Example:
// 60 = 2^2 × 3 × 5
// 🧠 Usage
// Divisor problems
// GCD/LCM optimization
// Number theory questions
// ⚙️ Algorithm
// Start with smallest prime (2)
// Divide until not divisible
// Move to next prime
// Repeat until number reduced to 1
// Optimization: Use precomputed primes (Sieve) for faster factorization




#include<bits/stdc++.h>
using namespace std;
vector<int> primeFactors(int n) {
    vector<int> factors;
    for(int i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }
    if(n > 1) factors.push_back(n);
    return factors;
}
int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    vector<int> factors = primeFactors(n);
    cout << "Prime factors of " << n << ": ";
    for(int factor : factors) {
        cout << factor << " ";
    }
    return 0;
}





// ⭐ 1.3 Smallest Prime Factor (SPF)
// 💡 Concept

// Precompute smallest prime divisor for each number.

// 👉 Allows factorization in O(log n)

// 🧠 Usage
// Fast multiple queries
// Competitive programming optimization





#include<bits/stdc++.h>
using namespace std;
vector<int> SPF(int n) {
    vector<int> spf(n+1);
    for(int i = 0; i <= n; i++) spf[i] = i;
    for(int i = 2; i * i <= n; i++) {
        if(spf[i] == i) {
            for(int j = i * i; j <= n; j += i) {
                if(spf[j] == j) spf[j] = i;
            }
        }
    }
    return spf;
}

// Factorization using SPF
vector<int> getFactor(int n, vector<int>& spf) {
    vector<int> res;
    while(n != 1) {
        res.push_back(spf[n]);
        n /= spf[n];
    }
    return res;
}
int main(){
    int n;
    cin>>n;
    vector<int>spf=SPF(n);
    cout<<"Smallest prime factors up to "<<n<<": ";
    for(int i=2;i<=n;i++){
        cout<<spf[i]<<endl<<" ";// SPF of 0 and 1 is not defined, so we start from 2 if n=60 
    }
    cout<<"\nPrime factors of "<<n<<" "<<endl;
    vector<int> factors = getFactor(n, spf);
    for(int factor : factors) {
        cout << factor << " ";// Output the prime factors of n
    }
    return 0;
}




// 🔹 2. MODULAR ARITHMETIC ADVANCED ⭐⭐⭐
// ⭐ 2.1 Modular Inverse
// 💡 Concept

// Find x such that:

// a * x ≡ 1 (mod m)
// 🧠 Usage
// Division in modulo
// nCr % MOD
// Probability problems
// ⚙️ Formula (Fermat-based)
// formula: a^(m-2) % m (when m is prime)
//a^-1=a^(m-2) mod m if m is prime
// ⚙️ Algorithm (Extended Euclidean)
// Extended Euclidean Algorithm to find x, y such that ax + by = gcd(a, b)
// If gcd(a, m) = 1, then x is the modular inverse of a mod m
// Works for non-prime m as well
// Time complexity: O(log m)


//node:🔥 BEST CP TEMPLATE
// PRIME MOD
// inverse = modPow(a, MOD-2, MOD);

// // NON PRIME MOD
// inverse = modInverseEEA(a, mod);
// ✅ INTERVIEW MEMORY TRICK

// Remember:

// Prime mod → Fermat
// Any mod → EEA

// 🔶 1) FERMAT’S LITTLE THEOREM METHOD ⭐⭐⭐
// This is most used in CP.
// 💡 Theory
// For prime modulus:
// a^(m-1) ≡ 1 (mod m) if m is prime and a is not divisible by m

// Multiply both sides by inverse of a:
// a^-1 ≡ a^(m-2) (mod m)

// ✅ Formula
// So inverse is:
// a^(m-2) % m



// 🔶 2) EXTENDED EUCLIDEAN ALGORITHM METHOD ⭐⭐⭐
// This is general-purpose modular inverse.
// Works even when modulus is not prime.

// 💡 Theory
// We know:
// ax+my=gcd(a,m)

// If:
// gcd(a,m)=1
// Then:
// ax+my=1

// Taking modulo m:
// ax ≡ 1 (mod m)
// So x is inverse.





#include<bits/stdc++.h>
using namespace std;
long long modPow(long long a,long long b,long long mod){
    long long res=1;
    while(b>0){
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
long long modInverseFermat(long long a,long long mod){
    return modPow(a,mod-2,mod);
}
long long gcdExtended(long long a,long long b,long long &x,long long &y){
    if(a==0){
        x=0;
        y=1;
        return b;

    }
    long long x1,y1;
    long long gcd=gcdExtended(b%a,a,x1,y1);
    x=y1-(b/a)*x1;
    y=x1;
    return gcd;

}
long long modInverseEEA(long long a,long long mod){
    long long x,y;
    long long g=gcdExtended(a,mod,x,y);
    if(g!=1) return -1; // Inverse doesn't exist
    return (x%mod+mod)%mod; // Ensure positive result
}
int main(){
    long long a,m;
    cout<<"Enter a and m: ";
    cin>>a>>m;
    cout<<"Modular Inverse of "<<a<<" mod "<<m<<" using Fermat's Little Theorem: "<<modInverseFermat(a,m)<<endl;// Note: This only works if m is prime
    cout<<"Modular Inverse of "<<a<<" mod "<<m<<" using Extended Euclidean Algorithm: "<<modInverseEEA(a,m)<<endl;// This works for any m, but a and m must be coprime
    return 0;
}



// ⭐ 2.2 Modular Division
// 💡 Concept
// To compute (a / b) % m, we can rewrite it as:
// (a * b^-1) % m
// Where b^-1 is the modular inverse of b mod m.
// 🧠 Usage
// Probability calculations
// nCr % MOD
// ⚙️ Algorithm
// Compute modular inverse of b (using Fermat or EEA)
// Multiply a by the inverse
// Take modulo m
// Time complexity: O(log m) for inverse + O(1) for multiplication
// Note: Ensure b and m are coprime for inverse to exist
// Example: (10 / 3) % 7
// Compute inverse of 3 mod 7 → 5 (since 3*5 % 7 = 1)
// Result = (10 * 5) % 7 = 50 % 7 = 1
// So (10 / 3) % 7 = 1



#include<bits/stdc++.h>
using namespace std;
long long modPow(long long a,long long b,long long mod){
    long long res=1;
    while(b>0){
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
long long modInverseFermat(long long a,long long mod){
    return modPow(a,mod-2,mod);
}
long long gcdExtended(long long a,long long b,long long &x,long long &y){
    if(a==0){
        x=0;
        y=1;
        return b;

    }
    long long x1,y1;
    long long gcd=gcdExtended(b%a,a,x1,y1);
    x=y1-(b/a)*x1;
    y=x1;
    return gcd;

}
long long modInverseEEA(long long a,long long mod){
    long long x,y;
    long long g=gcdExtended(a,mod,x,y);
    if(g!=1) return -1; // Inverse doesn't exist
    return (x%mod+mod)%mod; // Ensure positive result
}
long long modDivide(long long a,long long b,long long mod){
    long long inverse=modInverseFermat(b,mod); // Use Fermat's method for prime mod
    if(inverse==-1) return -1; // Inverse doesn't exist
    return (a*inverse)%mod;
}
int main(){
    long long a,b,m;
    cout<<"Enter a, b and m: ";
    cin>>a>>b>>m;
    cout<<"Modular Division of "<<a<<" by "<<b<<" mod "<<m<<" is: "<<modDivide(a,b,m)<<endl;// Note: This only works if m is prime and b is not divisible by m
    return 0;
}




// ⭐ 2.4 nCr % MOD
// 💡 Concept

// Precompute factorials + inverse factorials for O(1) nCr queries.
// 🧠 Usage
// Combinatorial problems
// Probability calculations
// ⚙️ Algorithm
// Precompute factorials: fact[i] = i! % mod
// Precompute inverse factorials: invFact[i] = (i!)^-1 % mod
// nCr(n, r) = fact[n] * invFact[r] * invFact[n-r] % mod
// Time complexity: O(n) for precomputation, O(1) for each nCr query
// Note: Ensure mod is prime for inverse factorials using Fermat's method
// Example: nCr(5, 2) % 7
// fact[5] = 120 % 7 = 1
// invFact[2] = 2^-1 % 7 = 4 (since 2*4 % 7 = 1)
// invFact[3] = 3^-1 % 7 = 5 (since 3*5 % 7 = 1)
// nCr(5, 2) = 1 * 4 * 5 % 7 = 20 % 7 = 6
// So nCr(5, 2) % 7 = 6
// Note: For large n, precomputation is essential to avoid timeouts in competitive programming.

// ✅ 1) LOGIC CHECK

// Your formula:

// nCr(n, r) mod MOD = (fact[n] * invFact[r] % MOD) * invFact[n-r] % MOD
// return (fact[n]*invFact[r] % MOD)*invFact[n-r] % MOD;
// Under modulo, division is replaced by inverse:

// modM=fact[n]⋅invFact[r]⋅invFact[n−r]modM
// Your code exactly does this:
// return (fact[n]*invFact[r] % MOD)*invFact[n-r] % MOD;


// ✅ 3) DRY RUN FOR n=5, r=2
// We need:
// 5C2 = 5! / (2! * 3!)
// 🔹 Step 1: Factorials
// fact[5] = 120
// fact[2] = 2
// fact[3] = 6
// 🔹 Step 2: Inverse factorials

// Need:

// invFact[2] = inverse(2) = 500000004
// invFact[3] = inverse(6) = 166666668

// under MOD = 1e9+7

// 🔹 Step 3: Apply formula
// 5C2 = fact[5] * invFact[2] * invFact[3]
// = 120 × inverse(2) × inverse(6)

// This simplifies to:

// = 10
// ✅ Final output = 10
//nCr(5, 2) % 1000000007 = 10




#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
const int MOD=1e9+7;
long long fact[N],invFact[N];

long long modPow(long long a, long long b, long long mod) {
    long long res = 1;
    while(b > 0) {
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
long long modInverseFermat(long long a, long long mod) {
    return modPow(a, mod - 2, mod);
}
void precomputeFactorials() {
    fact[0] = 1;
    for(int i = 1; i < N; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
    }
    invFact[N-1] = modInverseFermat(fact[N-1], MOD);
    for(int i = N-2; i >= 0; i--) {
        invFact[i] = (invFact[i+1] * (i+1)) % MOD;
    }
}
long long nCr(int n, int r){
    if(r>n||r<0) return 0;
    return (fact[n]*invFact[r] % MOD)*invFact[n-r] % MOD;
}
int main() {
    precomputeFactorials();
    int n, r;
    cout << "Enter n and r: ";
    cin >> n >> r;
    cout << "nCr(" << n << ", " << r << ") % " << MOD << " = " << nCr(n, r) << endl;
    return 0;
}








// 🔹 3. COMBINATORICS ⭐⭐⭐
// ⭐ 3.1 Pascal’s Triangle
// 💡 Concept
// C(n,r)=C(n−1,r−1)+C(n−1,r)

// 🧠 Usage
// DP-based nCr
// Counting problems
// ⚙️ Algorithm
// Create a 2D array C[n+1][n+1]
// Base cases: C[i][0] = C[i][i] = 1
// Fill using the relation:
// C[i][j] = C[i-1][j-1] + C[i-1][j]
// Time complexity: O(n^2) for precomputation, O(1) for each query
// Example: C(5, 2)
// C(5, 2) = C(4, 1) + C(4, 2)
// C(4, 1) = C(3, 0) + C(3, 1) = 1 + 3 = 4
// C(4, 2) = C(3, 1) + C(3, 2) = 3 + 3 = 6
// So C(5, 2) = 4 + 6 = 10
// This matches the known value of 5C2 = 10
// Note: This method is not efficient for large n due to O(n^2) complexity, but it's a good educational tool to understand combinatorial relationships. For large n, use factorial-based methods with modular arithmetic.



#include<bits/stdc++.h>
using namespace std;
const int PAS_N = 1000;
vector<vector<long long>> C;
void precomputePascal() {
    C.assign(PAS_N, vector<long long>(PAS_N, 0));
    for(int i = 0; i < PAS_N; i++) {
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; j++) {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
}
int main() {
    precomputePascal();
    int n, r;
    cout << "Enter n and r: ";
    cin >> n >> r;
    if(n < 0 || n >= PAS_N || r > n || r < 0) {
        cout << "Invalid input. n must be in [0, " << PAS_N - 1 << "] and r must be between 0 and n." << endl;
        return 0;
    }
    cout << "C(" << n << ", " << r << ") = " << C[n][r] << endl;
    return 0;
}




// ⭐ 3.2 Inclusion-Exclusion Principle ⭐⭐⭐
// 💡 Concept
// The inclusion-exclusion principle is a counting technique used to calculate the size of the union of multiple sets by including and excluding the sizes of their intersections.
// 🧠 Usage
// Counting problems with overlapping constraints
// ⚙️ Algorithm
// For a collection of sets A1, A2, ..., An, the principle states:
// |A1 ∪ A2 ∪ ... ∪ An| = Σ|Ai| - Σ|Ai ∩ Aj| + Σ|Ai ∩ Aj ∩ Ak| - ... + (-1)^(n+1) |A1 ∩ A2 ∩ ... ∩ An|
// Time complexity: O(2^n) for generating all subsets, O(n) for each subset operation
// Example: Counting numbers from 1 to 100 that are divisible by 2 or 3
// Let A be the set of numbers divisible by 2, B be the set of numbers divisible by 3
// |A| = 50, |B| = 33, |A ∩ B| = 16
// |A ∪ B| = 50 + 33 - 16 = 67
// So there are 67 numbers from 1 to 100 that are divisible by 2 or 3
// Note: This principle is powerful for solving complex counting problems where direct counting is difficult due to
// overlapping conditions. It helps to avoid double-counting by systematically including and excluding intersections of sets.
// Example: Counting numbers from 1 to 100 that are divisible by 2, 3, or 5
// Let A be the set of numbers divisible by 2, B be the set of numbers
// divisible by 3, C be the set of numbers divisible by 5
// |A| = 50, |B| = 33, |C| = 20
// |A ∩ B| = 16, |A ∩ C| = 10, |B ∩ C| = 6
// |A ∩ B ∩ C| = 3
// |A ∪ B ∪ C| = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74
// So there are 74 numbers from 1 to 100 that are divisible by 2, 3, or 5
// This example demonstrates how the inclusion-exclusion principle can be applied to count the number of elements in the union of multiple sets while accounting for overlaps.

// ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣

// P(A∪B)=P(A)+P(B)−P(A∩B)≈0.80
// If we want to find the probability of at least one of two events A and B occurring, we can use the inclusion-exclusion principle. The formula is:
// P(A∪B)=P(A)+P(B)−P(A∩B)
// This formula accounts for the fact that if we simply added P(A) and P(B),
// we would be double-counting the probability of both events occurring together (P(A∩B)). By subtracting P(A∩B), we ensure that we only count the probability of each event once.
// Example: If P(A) = 0.5, P(B) = 0.4, and P(A∩B) = 0.1, then:
// P(A∪B) = 0.5 + 0.4 - 0.1 = 0.8
// So the probability of at least one of the events A or B occurring is 0.
//80.
// 🧠 Usage
// Counting with overlaps
// Multiples problems
// Probability




#include<bits/stdc++.h>
using namespace std;
int countMultiples(int n){
    return n/2 + n/3 - n/6; // Count of multiples of 2 + Count of multiples of 3 - Count of multiples of 6 (to avoid double counting)
}
int main(){
    int n;
    cout<<"Enter a number: ";
    cin>>n;
    cout<<"Count of numbers from 1 to "<<n<<" that are multiples of 2 or 3: "<<countMultiples(n)<<endl;
    return 0;
}



// 🔹 4. GCD BASED PROBLEMS
// ⭐ 4.1 Extended Euclidean Algorithm ⭐⭐
// 💡 Concept

// Find x, y such that:
// ax+by=gcd(a,b)
// 🧠 Usage
// Modular inverse
// Diophantine equations
// ⚙️ Algorithm
// Base case: if a=0, return (0, 1)
// Recursive case: gcd(b%a, a) to find x1, y1
// Update x, y using results from recursive call
// Time complexity: O(log(min(a, b)))
// Example: Extended Euclidean Algorithm for a=30, b=21
// gcd(30, 21) = 3
// We want to find x, y such that:
// 30x + 21y = 3
// Using the algorithm, we find:
// x = 7, y = -10
// So one solution to the equation is:
// 30*7 + 21*(-10) = 210 - 210 = 3
// Note: The Extended Euclidean Algorithm is a powerful tool for solving linear Diophantine
// equations and finding modular inverses, especially when the modulus is not prime. It provides a way to express the greatest common divisor of two numbers as a linear combination of those numbers, which is essential for many applications in number theory and cryptography.




#include<bits/stdc++.h>
using namespace std;
int extendedGCD(int a, int b, int &x, int &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int g = extendedGCD(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}
int main() {
    int a, b;
    cout << "Enter two numbers: ";
    cin >> a >> b;
    int x, y;
    int g = extendedGCD(a, b, x, y);
    cout << "GCD: " << g << endl;
    cout << "Coefficients x and y such that " << a << "*x + " << b << "*y = GCD: " << x << ", " << y << endl;
    return 0;
}




// ⭐ 4.2 Linear Diophantine Equation
// 💡 Concept

// Solve:

// ax + by = c
// Solution exists if:
// gcd(a,b) divides c
// 🧠 Usage
// Number theory problems
// Integer solutions
// ⚙️ Algorithm
// Step 1: Compute g = gcd(a, b) using Extended Euclidean Algorithm
// Step 2: Check if g divides c. If not, no solutions.
// Step 3: If g divides c, divide the equation by g:
// (a/g)x + (b/g)y = c/g
// Step 4: Use Extended Euclidean Algorithm to find one particular solution (x0, y0) to the reduced equation.
// Step 5: General solution can be expressed as:
// x = x0 + k*(b/g)
// y = y0 - k*(a/g)
// where k is any integer.
// Time complexity: O(log(min(a, b))) for Extended Euclidean Algorithm
// Example: Solve 30x + 21y = 3
// Step 1: g = gcd(30, 21) = 3
// Step 2: 3 divides 3, so solutions exist.
// Step 3: Divide the equation by 3:
// 10x + 7y = 1
// Step 4: Use Extended Euclidean Algorithm to find a particular solution:
// One solution is x0 = 5, y0 = -7 (since 10*5 + 7*(-7) = 50 - 49 = 1)
// Step 5: General solution:
// x = 5 + k*7
// y = -7 - k*10
// where k is any integer.
// So the integer solutions to the equation 30x + 21y = 3 can be expressed as:
// x = 5 + 7k
// y = -7 - 10k
// for any integer k. This means there are infinitely many integer solutions to the equation, depending on the value of k.




#include<bits/stdc++.h>
using namespace std;
bool solve(int a, int b, int c, int &x, int &y) {
    int g = extendedGCD(a, b, x, y);
    if(c % g != 0) return false;

    x *= c/g;
    y *= c/g;
    return true;
}
int extendedGCD(int a, int b, int &x, int &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int g = extendedGCD(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}
int main() {
    int a, b, c;
    cout << "Enter a, b and c: ";
    cin >> a >> b >> c;
    int x, y;
    if(solve(a, b, c, x, y)) {
        cout << "One solution to the equation " << a << "*x + " << b << "*y = " << c << " is: x = " << x << ", y = " << y << endl;
    } else {
        cout << "No solutions exist for the equation " << a << "*x + " << b << "*y = " << c << endl;
    }
    return 0;
}






// 🔹 5. NUMBER PROPERTIES
// ⭐ 5.1 Perfect Number
// 💡 Concept

// Sum of proper divisors = number
// Example: 6 (divisors: 1, 2, 3; sum = 6)
// 🧠 Usage
// Number theory problems
// Divisor-related questions
// ⚙️ Algorithm
// For a number n, find all proper divisors (1 to n/2)
// Sum them up and compare with n
// Time complexity: O(n) for finding divisors, can be optimized to O(sqrt(n)) by only checking up to sqrt(n) and adding both divisors when a divisor is found
// Example: Check if 28 is a perfect number
// Proper divisors of 28: 1, 2, 4, 7, 14
// Sum = 1 + 2 + 4 + 7 + 14 = 28
// Since the sum of proper divisors equals 28, it is a perfect number.



#include<bits/stdc++.h>
using namespace std;
bool isPerfect(int n) {
    int sum = 1;
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            sum += i;
            if(i != n/i) sum += n/i;
        }
    }
    return sum == n && n != 1;
}
int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    if(isPerfect(n)) {
        cout << n << " is a perfect number." << endl;
    } else {
        cout << n << " is not a perfect number." << endl;
    }
    return 0;
}





// ⭐ 5.2 Armstrong Number
// 💡 Concept

// Sum of digits^power = number
// Example: 153 (1^3 + 5^3 + 3^3 = 153)
// 🧠 Usage
// Number theory problems
// Digit-related questions
// ⚙️ Algorithm
// Convert number to string to easily access digits
// Calculate the number of digits (power)
// Sum the digits raised to the power
// Compare the sum with the original number
// Time complexity: O(d) where d is the number of digits in the number
// Example: Check if 9474 is an Armstrong number
// Number of digits = 4
// Sum = 9^4 + 4^4 + 7^4 + 4^4 = 6561 + 256 + 2401 + 256 = 9474
// Since the sum equals the original number, 9474 is an Armstrong number.


#include<bits/stdc++.h>
using namespace std;
bool isArmstrong(int n) {
    int temp = n, sum = 0, digits = 0;
    while(temp) {
        digits++;
        temp /= 10;
    }
    temp = n;
    while(temp) {
        int d = temp % 10;
        sum += pow(d, digits);
        temp /= 10;
    }
    return sum == n;
}
int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    if(isArmstrong(n)) {
        cout << n << " is an Armstrong number." << endl;
    } else {
        cout << n << " is not an Armstrong number." << endl;
    }
    return 0;
}




// ⭐ 5.3 Trailing Zeros in Factorial ⭐⭐
// 💡 Concept

// Count number of factors of 5

// ⚙️ Formula
// Trailing zeros in n! = n/5 + n/25 + n/125 + ...
// 🧠 Usage
// Factorial-related problems
// Number theory questions
// ⚙️ Algorithm
// Initialize count = 0
// For i = 5; n/i >= 1; i *= 5:
// count += n/i
// Time complexity: O(log_5(n))
// Example: Count trailing zeros in 100!



#include<bits/stdc++.h>
using namespace std;
int countTrailingZeros(int n) {
    int count = 0;
    for(int i = 5; n/i >= 1; i *= 5) {
        count += n/i;
    }
    return count;
}
int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    cout << "Number of trailing zeros in " << n << "! is: " << countTrailingZeros(n) << endl;
    return 0;
}