Вже доступно! Дослідження Telegram за 2025 — головні інсайти року 
Tech Jargon - Decoded
Відкрити в Telegram
Confused by tech terms? Don’t worry, we’ve got you 🤝 We make things simple, one concept at a time. Learn daily Easy & clear Turn Confusion into clarity. #tech #it #softwareengineer #cs #development
Показати більше2 015
Підписники
-124 години
-57 днів
-4030 день
Архів дописів
Fast Fibonacci using Matrix Exponentiation
public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
int[][] baseMatrix = {{1, 1}, {1, 0}};
int[][] resultMatrix = matrixPower(baseMatrix, n - 1);
return resultMatrix[0][0];
}
private static int[][] matrixPower(int[][] matrix, int n) {
int[][] result = {{1, 0}, {0, 1}}; // Identity matrix
int[][] base = matrix;
while (n > 0) {
if ((n & 1) == 1) { // If n is odd
result = matrixMultiply(result, base);
}
base = matrixMultiply(base, base);
n >>= 1; // Divide n by 2
}
return result;
}
private static int[][] matrixMultiply(int[][] a, int[][] b) {
int[][] result = new int[2][2];
result[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
result[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
result[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
result[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
return result;
}
public static void main(String[] args) {
int n = 10;
System.out.println("Fibonacci(" + n + ") = " + fibonacci(n));
}
}Modular Multiplicative Inverse
public class ModularInverse {
public static int modInverse(int a, int m) {
if (m == 1) return 0;
int m0 = m, y = 0, x = 1;
while (a > 1) {
int q = a / m;
int t = m;
m = a % m;
a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0)
x += m0;
return x;
}
public static void main(String[] args) {
int a = 3;
int m = 11;
int inverse = modInverse(a, m);
System.out.println("Modular multiplicative inverse of " + a + " under modulo " + m + " is " + inverse);
}
}Modular Exponentiation
public class ModularExponentiation {
public static long modularExponentiation(long base, long exponent, long modulus) {
long result = 1;
base = base % modulus;
while (exponent > 0) {
if (exponent % 2 == 1) {
result = (result * base) % modulus;
}
base = (base * base) % modulus;
exponent = exponent >> 1;
}
return result;
}
public static void main(String[] args) {
long base = 2;
long exponent = 10;
long modulus = 1000;
long result = modularExponentiation(base, exponent, modulus);
System.out.println("Result: " + result);
}
}Modular Exponentiation
public class ModularExponentiation {
public static long modularExponentiation(long base, long exponent, long modulus) {
long result = 1;
base = base % modulus;
while (exponent > 0) {
if (exponent % 2 == 1) {
result = (result * base) % modulus;
}
base = (base * base) % modulus;
exponent = exponent >> 1;
}
return result;
}
public static void main(String[] args) {
long base = 2;
long exponent = 10;
long modulus = 1000;
long result = modularExponentiation(base, exponent, modulus);
System.out.println("Result: " + result);
}
}Count Primes Less than N
public class PrimeCounter {
public static int countPrimes(int n) {
if (n <= 2) {
return 0;
}
boolean[] isPrime = new boolean[n];
for (int i = 2; i < n; i++) {
isPrime[i] = true;
}
for (int i = 2; i * i < n; i++) {
if (!isPrime[i]) {
continue;
}
for (int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
int count = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) {
count++;
}
}
return count;
}
public static void main(String[] args) {
int n = 10;
int primeCount = countPrimes(n);
System.out.println("Number of primes less than " + n + " is: " + primeCount);
}
}Fast Fibonacci using Matrix Exponentiation
public class FastFibonacci {
public static long fibonacci(int n) {
if (n <= 1) {
return n;
}
long[][] matrix = {{1, 1}, {1, 0}};
long[][] result = matrixPower(matrix, n - 1);
return result[0][0];
}
private static long[][] matrixPower(long[][] matrix, int n) {
if (n == 0 || n == 1) {
return n == 0 ? new long[][]{{1, 0}, {0, 1}} : matrix;
}
long[][] halfPower = matrixPower(matrix, n / 2);
long[][] result = multiplyMatrices(halfPower, halfPower);
if (n % 2 != 0) {
result = multiplyMatrices(result, matrix);
}
return result;
}
private static long[][] multiplyMatrices(long[][] a, long[][] b) {
long[][] result = new long[2][2];
result[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
result[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
result[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
result[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
return result;
}
public static void main(String[] args) {
int n = 10;
System.out.println("Fibonacci(" + n + ") = " + fibonacci(n));
}
}Modular Multiplicative Inverse
public class ModularInverse {
public static int modInverse(int a, int m) {
a = a % m;
for (int x = 1; x < m; x++) {
if ((a * x) % m == 1) {
return x;
}
}
return -1; // Inverse doesn't exist
}
public static void main(String[] args) {
int a = 3;
int m = 11;
int inverse = modInverse(a, m);
if (inverse != -1) {
System.out.println("Modular multiplicative inverse of " + a + " modulo " + m + " is " + inverse);
} else {
System.out.println("Modular multiplicative inverse of " + a + " modulo " + m + " does not exist");
}
}
}Count Digits Without % or /
public class DigitCounter {
public static int countDigits(int num) {
if (num == 0) {
return 1;
}
int count = 0;
int temp = Math.abs(num);
while (temp > 0) {
temp = temp - (int)Math.pow(10, (int)(Math.log10(temp)));
count++;
}
return count;
}
public static void main(String[] args) {
System.out.println(countDigits(12345));
System.out.println(countDigits(-987));
System.out.println(countDigits(0));
}
}Swap Two Numbers Without Temp
public class SwapNumbers {
public static void main(String[] args) {
int a = 5;
int b = 10;
a = a + b;
b = a - b;
a = a - b;
System.out.println("a = " + a + ", b = " + b);
}
}Modular Multiplicative Inverse
public class ModularInverse {
public static int modInverse(int a, int m) {
a = a % m;
for (int x = 1; x < m; x++)
if ((a * x) % m == 1)
return x;
return -1; // Inverse doesn't exist
}
public static void main(String[] args) {
int a = 3;
int m = 11;
int inverse = modInverse(a, m);
if (inverse != -1) {
System.out.println("Modular multiplicative inverse of " + a + " under modulo " + m
+ " is " + inverse);
} else {
System.out.println("Modular multiplicative inverse doesn't exist for " + a + " under modulo " + m);
}
}
}