basic-level-math.cpp

// 🔹 Basic Arithmetic & Properties
// Prime numbers (check prime) ⭐
// Factors / Divisors of a number
// GCD (Euclidean Algorithm) ⭐⭐⭐
// LCM using GCD
// Even / Odd properties
// 🔹 Modular Arithmetic (Intro)
// Modulo properties (a+b)%m, (a*b)%m ⭐⭐⭐
// Handling overflow using modulo
// Basic modular addition & multiplication
// 🔹 Exponentiation
// Fast exponentiation (Binary Exponentiation) ⭐⭐⭐
// Power with modulo
// 🔹 Counting Basics
// Factorial
// Permutations (nPr)
// Combinations (nCr basic)
// 🔹 Simple Problem Types
// Sum of digits
// Reverse number
// Palindrome number

// 👉 Goal: Build strong math intuition





// 🔹 1. Prime Numbers (Check Prime) ⭐
// 💡 Concept

// A number is prime if it has exactly 2 divisors: 1 and itself.

// 👉 Key optimization:
// Check divisibility only up to √n
// Reason: factors come in pairs.

// 🧠 Usage in CP/OA
// Number theory problems
// Sieve-based precomputation
// Cryptography basics
// Prime factorization
// ⚙️ Algorithm
// for i = 2 → sqrt(n)
//     if n % i == 0 → not prime




#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n){
    if(n<=1) return false; // 0 and 1 are not prime
    for(int i=2; i*i<=n; i++){
        if(n%i==0) return false; // n is divisible by i, hence not prime
    }
    return true;
}
int main(){
    int n;
    cout<<"Enter a number: ";
    cin>>n;
    if(isPrime(n)){
        cout<<n<<" is a prime number."<<endl;
    } else {
        cout<<n<<" is not a prime number."<<endl;
    }
    return 0;
}




// 🔹 2. Factors / Divisors
// 💡 Concept

// Divisors come in pairs:
// If i divides n, then n/i also divides n.

// 🧠 Usage
// Divisor count problems
// Optimization problems
// Number theory tasks
// ⚙️ Algorithm

// Loop till √n
// for i = 1 → sqrt(n)
//     if n % i == 0
//         count++ // i is a divisor
//         if i != n/i
//             count++ // n/i is also a divisor





#include<bits/stdc++.h>
using namespace std;
vector<int>getDivisors(int n){
    vector<int>divisors;
    for(int i=1;i*i<=n;i++){
        if(n%i==0){
            divisors.push_back(i); // i is a divisor
            if(i!=n/i){ // Avoid adding the square root twice for perfect squares
                divisors.push_back(n/i); // n/i is also a divisor
            }
        }
    }
    return divisors;
}
int main(){
    int n;
    cout<<"Enter a number: ";
    cin>>n;
    vector<int>divisors = getDivisors(n);
    cout<<"Divisors of "<<n<<": ";
    for(int d : divisors){
        cout<<d<<" ";
    }
    cout<<endl;
    return 0;
}







// 🔹 3. GCD (Euclidean Algorithm) ⭐⭐⭐
// 💡 Concept

// GCD(a, b) = GCD(b, a % b)

// 👉 Based on:
// Greatest common divisor remains same after modulo reduction

// 🧠 Usage
// Fractions simplification
// LCM calculation
// Number theory
// Competitive problems (very common)
// ⚙️ Algorithm

// Repeat until b = 0




#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(b==0) return a;// Base case: GCD of a and 0 is a
    return gcd(b,a%b);// Recursive call: GCD of b and a mod b
}
int main(){
    int a,b;
    cout<<"Enter two numbers: ";
    cin>>a>>b;
    cout<<"GCD of "<<a<<" and "<<b<<" is: "<<gcd(a,b)<<endl;
    return 0;
}






// 🔹 4. LCM using GCD
// 💡 Concept
// LCM(a, b) = (a * b) / GCD(a, b)
// 🧠 Usage
// Scheduling problems
// Cycles
// Repeating patterns




#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return (a / gcd(a,b)) * b; // To avoid overflow, divide before multiplying
}
int main(){
    int a,b;
    cout<<"Enter two numbers: ";
    cin>>a>>b;
    cout<<"LCM of "<<a<<" and "<<b<<" is: "<<lcm(a,b)<<endl;
    return 0;
}





// 🔹 5. Even / Odd Properties
// 💡 Concept
// Even → divisible by 2
// Odd → not divisible
// 🧠 Usage
// Bit manipulation
// Pattern problems
// Optimization
// ⚙️ Algorithm
// if n % 2 == 0 → even
// else → odd
// Bitwise check: if (n & 1) → odd, else → even






#include<bits/stdc++.h>
using namespace std;
bool isEven(int n){
    return (n % 2 == 0); // Check if n is divisible by 2
}
bool isOdd(int n){
    return (n % 2 != 0); // Check if n is not divisible by 2
}
bool isEvenFast(int n){
    return (n & 1) == 0; // Bitwise check: if the least significant bit is 0, it's even
}
bool isOddFast(int n){
    return (n & 1) == 1; // Bitwise check: if the least significant bit is 1, it's odd
}
int main(){
    int n;
    cout<<"Enter a number: ";
    cin>>n;
    if(isEven(n)){
        cout<<n<<" is an even number."<<endl;
    } else {
        cout<<n<<" is an odd number."<<endl;
    }
    // Using bitwise checks
    if(isEvenFast(n)){
        cout<<n<<" is an even number (bitwise check)."<<endl;
    } else {
        cout<<n<<" is an odd number (bitwise check)."<<endl;
    }
    return 0;
}






// 🔹 6. Modular Arithmetic ⭐⭐⭐
// 💡 Concept
// (a + b) % m = ((a % m) + (b % m)) % m
// (a * b) % m = ((a % m) * (b % m)) % m
// 🧠 Usage
// Avoid overflow
// Huge numbers (10^18+)
// Standard in CP (mod = 1e9+7)



#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7; // Common modulus used in competitive programming
int modAdd(int a, int b) {
    return ((a % MOD) + (b % MOD)) % MOD; // Modular addition
}
int modMul(int a, int b) {
    return ((a % MOD) * (b % MOD)) % MOD; // Modular multiplication
}
int main() {
    int a, b;
    cout << "Enter two numbers: ";
    cin >> a >> b;
    cout << "Modular addition: " << modAdd(a, b) << endl;
    cout << "Modular multiplication: " << modMul(a, b) << endl;
    return 0;
}




// 🔹 7. Fast Exponentiation ⭐⭐⭐
// 💡 Concept

// Instead of O(n), reduce to O(log n)

// Binary representation of power:

// a^13 = a^(1101)
// 🧠 Usage
// Power calculation
// Modular exponentiation
// Cryptography
// DP optimizations
// ⚙️ Formula (core)
// if n is even → a^n = (a^(n/2))^2
// if n is odd → a^n = a * (a^(n-1))
// Implementation
// Recursive or iterative (bit manipulation)
// Handle modulo if needed




#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7; // Common modulus used in competitive programming
long long power(long long a,long long b){
    long long result=1;
    while(b>0){
        if(b&1) result*=a;
        a*=a;
        b>>=1;
    }
    return result;
}
int main(){
    long long a,b;
    cout<<"Enter base and exponent: ";
    cin>>a>>b;
    cout<<a<<" raised to the power "<<b<<" is: "<<power(a,b)<<endl;
    return 0;
}





// 🔹 8. Power with Modulo
// 💻 Code



#include<bits/stdc++.h>
using namespace std;
long long modPow(long long a, long long b, int mod) {
    long long res = 1;
    while(b > 0) {
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
int main() {
    long long a, b;
    int mod;
    cout << "Enter base, exponent and modulus: ";
    cin >> a >> b >> mod;
    cout << a << " raised to the power " << b << " modulo " << mod << " is: " << modPow(a, b, mod) << endl;
    return 0;
}





// 🔹 9. Factorial
// 💡 Concept
// n! = n * (n-1) * ... * 1
// 🧠 Usage
// Permutations & combinations
// Counting problems
// DP optimizations
// ⚙️ Algorithm
// Iterative or recursive
// Handle large n with modulo if needed
// Precompute factorials for multiple queries



#include<bits/stdc++.h>
using namespace std;
long long factorial(int n) {
    long long res = 1;
    for(int i = 2; i <= n; i++)
        res *= i;
    return res;
}
int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    cout << "Factorial of " << n << " is: " << factorial(n) << endl;
    return 0;
}








// 🔹 10. Permutations (nPr)
// 💡 Formula
// nPr = n! / (n-r)!
// 🧠 Usage
// Arrangements
// Counting problems
// ⚙️ Algorithm
// Calculate factorials
// Handle large n with modulo if needed
// Precompute factorials for multiple queries


#include<bits/stdc++.h>
using namespace std;

long long factorial(int n) {
    long long res = 1;
    for(int i = 2; i <= n; i++)
        res *= i;
    return res;
}
long long nPr(int n, int r) {
    if(r > n) return 0; // More items than available
    return factorial(n) / factorial(n - r); // n! / (n-r)!
}
int main() {
    int n, r;
    cout << "Enter n and r: ";
    cin >> n >> r;
    cout << "nPr of " << n << " and " << r << " is: " << nPr(n, r) << endl;
    return 0;
}




// 🔹 11. Combinations (nCr)
// 💡 Formula
	// nCr = n! / (r! * (n-r)!)
// 🧠 Usage
// Counting subsets
// Probability
// DP problems


#include<bits/stdc++.h>
using namespace std;
long long nCr(int n, int r) {
    if(r > n) return 0;
    long long res = 1;
    for(int i = 1; i <= r; i++) {
        res = res * (n - i + 1) / i;
    }
    return res;
}
int main() {
    int n, r;
    cout << "Enter n and r: ";
    cin >> n >> r;
    cout << "nCr of " << n << " and " << r << " is: " << nCr(n, r) << endl;
    return 0;
}




// 🔹 12. Sum of Digits
// 💡 Concept

// Repeatedly extract digits using %10 and /10
// 🧠 Usage
// Digit-based problems
// ⚙️ Algorithm
// int sumOfDigits(int n) {
//     int sum = 0;
//     while(n > 0) {
//         sum += n % 10; // Add last digit to sum
//         n /= 10; // Remove last digit
//     }



#include<bits/stdc++.h>
using namespace std;
int sumOfDigits(int n) {
    int sum = 0;
    while(n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    cout << "Sum of digits of " << n << " is: " << sumOfDigits(n) << endl;
    return 0;
}





//🔹 13. Reverse Number
// 💡 Concept
// Extract digits and build reversed number
// 🧠 Usage




#include<bits/stdc++.h>
using namespace std;
int reverseNumber(int n) {
    int rev = 0;
    while(n > 0) {
        rev = rev * 10 + (n % 10);
        n /= 10;
    }
    return rev;
}
int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    cout << "Reversed number of " << n << " is: " << reverseNumber(n) << endl;
    return 0;
}



// 🔹 14. Palindrome Number
// 💡 Concept

// Number == Reverse(number)
// 🧠 Usage
// Palindrome checks
// String-based problems
// ⚙️ Algorithm
// Reverse the number and compare with original
// Handle negative numbers (not palindrome)




#include<bits/stdc++.h>
using namespace std;
bool isPalindrome(int n) {
    int original = n;
    int rev = 0;
    while(n > 0) {
        rev = rev * 10 + (n % 10);
        n /= 10;
    }
    return original == rev;
}
int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    if(isPalindrome(n)) {
        cout << n << " is a palindrome number." << endl;
    } else {
        cout << n << " is not a palindrome number." << endl;
    }
    return 0;
}