```// Efficient Method : Time Complexity : θ(logn), Auxiliary Space: θ(1)

import java.io.*;
import java.util.*;

public class Main {

static int power(int x, int n)
{
int res = 1;

while(n>0)
{
if(n%2 != 0)
{
res = res * x;
x = x*x;
n = n/2;
}
else
{
x = x*x;
n = n/2;
}
}

return res;
}

public static void main (String[] args) {

int x = 3, n = 4;

System.out.println(power(x, n));

}
}```
```// Efficient Method : Time Complexity : θ(logn), Auxiliary Space: θ(logn)

import java.io.*;
import java.util.*;

public class Main {

static int power(int x, int n)
{
if(n == 0)
return 1;

int temp = power(x, n/2);

temp = temp * temp;

if(n % 2 == 0)
return temp;
else
return temp * x;
}

public static void main (String[] args) {

int x = 3, n = 5;

System.out.println(power(x, n));

}
}

// Naive Method : Time Complexity : θ(n)

static int power(int x, int n)
{
int res = 1;

for(int i=0; i<n; i++)
{
res = res * x;
}

return res;
}```
```// Shorter Implementation of the optimized sieve :

import java.io.*;
import java.util.*;

public class Main {

static void sieve(int n)
{
if(n <= 1)
return;

boolean isPrime[] = new boolean[n+1];

Arrays.fill(isPrime, true);

for(int i=2; i <= n; i++)
{
if(isPrime[i])
{
System.out.print(i+" ");
for(int j = i*i; j <= n; j = j+i)
{
isPrime[j] = false;
}
}
}
}

public static void main (String[] args) {

int n = 23;

sieve(n);

}
}

//Optimized Implementation : Time Complexity : O(nloglogn), Auxiliary Space : O(n)

static void sieve(int n)
{
if(n <= 1)
return;

boolean isPrime[] = new boolean[n+1];

Arrays.fill(isPrime, true);

for(int i=2; i*i <= n; i++)
{
if(isPrime[i])
{
for(int j = i*i; j <= n; j = j+i) // Replaced 2*i by i*i
{
isPrime[j] = false;
}
}
}

for(int i = 2; i<=n; i++)
{
if(isPrime[i])
System.out.print(i+" ");
}
}

//Simple Implementation of Sieve :

static void sieve(int n)
{
if(n <= 1)
return;

boolean isPrime[] = new boolean[n+1];

Arrays.fill(isPrime, true);

for(int i=2; i*i <= n; i++)
{
if(isPrime[i])
{
for(int j = 2*i; j <= n; j = j+i)
{
isPrime[j] = false;
}
}
}

for(int i = 2; i<=n; i++)
{
if(isPrime[i])
System.out.print(i+" ");
}
}

//Naive Solution : Time Complexity : O(n(sqrt(n))

static boolean isPrime(int n)
{
if(n==1)
return false;

if(n==2 || n==3)
return true;

if(n%2==0 || n%3==0)
return false;

for(int i=5; i*i<=n; i=i+6)
{
if(n % i == 0 || n % (i + 2) == 0)
return false;
}

return true;
}

static void printPrimes(int n)
{
for(int i = 2; i<=n; i++)
{
if(isPrime[i])
System.out.print(i+" ");
}
}```
```// Efficient Code with Sorted Order

static void printDivisors(int n)
{
int i = 1;
// Print all divisors from 1(inlcusive) to sqrt(n) (exclusive)
for(i=1; i*i < n; i++)
{
if(n % i == 0)
{
System.out.print(i+" ");
}
}
// Print all divisors from sqrt(n)(inlcusive) to n (inclusive)
for(; i >= 1; i--)
{
if(n % i == 0)
{
System.out.print((n / i)+" ");
}
}
}

//Efficient Code : Time Complexity: O(sqrt(n)) , Auxiliary Space : O(1)

static void printDivisors(int n)
{
for(int i=1; i*i <= n; i++)
{
if(n % i == 0)
{
System.out.print(i+" ");

if(i != n / i)
System.out.print((n / i)+" ");
}
}
}

// Naive Solution : Time Complexity : O(n) , Auxiliary Space : O(1)

static void printDivisors(int n)
{
for (int i=1;i<=n;i++)
if (n%i==0)
System.out.print(i+" ");
}```
```//Prime Factors in java
//More Efficient Solution : Time Complexity : O(sqrt(n))

import java.io.*;
import java.util.*;

public class Main {

static void printPrimeFactors(int n)
{
if(n <= 1)
return;

while(n % 2 == 0)
{
System.out.print(2+" ");

n = n / 2;
}

while(n % 3 == 0)
{
System.out.print(3+" ");

n = n / 3;
}

for(int i=5; i*i<=n; i=i+6)
{
while(n % i == 0)
{
System.out.print(i+" ");

n = n / i;
}

while(n % (i + 2) == 0)
{
System.out.print((i + 2)+" ");

n = n / (i + 2);
}
}

if(n > 3)
System.out.print(n+" ");

System.out.println();
}

public static void main (String[] args) {

int n = 450;

printPrimeFactors(n);

}
}

//Efficient Code :

static void printPrimeFactors(int n)
{
if(n <= 1)
return;

for(int i=2; i*i<=n; i++)
{
while(n % i == 0)
{
System.out.print(i+" ");

n = n / i;
}
}

if(n > 1)
System.out.print(n+" ");

System.out.println();
}

// Naive Method : Time Complexity : O(n^2(logn))

static boolean isPrime(int n)
{
if(n==1)
return false;

if(n==2 || n==3)
return true;

if(n%2==0 || n%3==0)
return false;

for(int i=5; i*i<=n; i=i+6)
{
if(n % i == 0 || n % (i + 2) == 0)
return false;
}

return true;
}

static void PrimeFactors(int n)
{
for(int i=2; i<n; i++)
{
if(isPrime(i))
{
int x = i;
while(n%x == 0)
{
System.out.print(i+" ");
x = x*i;
}
}
}
}```
```// Time Complexity: O(N^1/2), Auxilliary Space: O(1)
//More Efficient Code(for large numbers)
//Almost 3x faster than Efficient Solution

import java.io.*;
import java.util.*;

public class Main {

static boolean isPrime(int n)
{
if(n==1)
return false;

if(n==2 || n==3)
return true;

if(n%2==0 || n%3==0)
return false;

for(int i=5; i*i<=n; i=i+6)
{
if(n % i == 0 || n % (i + 2) == 0)
return false;
}

return true;
}

//DRIVER CODE
public static void main (String[] args) {

//taking input using Scanner class
Scanner sc=new Scanner(System.in);

int T=sc.nextInt();//input testcases

while(T-->0)//while testcase have not been exhausted
{
Solution obj=new Solution ();
int N;
N=sc.nextInt();//input n
if(obj.isPrime(N))
System.out.println("Yes");
else
System.out.println("No");

}

}
}

//Efficient Code : Time Complexity : O(sqrt(n))

static boolean isPrime(int n)
{
if(n==1)
return false;

for(int i=2; i*i<=n; i++)
{
if(n % i == 0)
return false;
}

return true;
}

// Naive Method : Time Complexity : O(n)

static boolean isPrime(int n)
{
if(n == 1)
return false;
for(int i=2; i<n; i++)
{
if(n%i == 0)
return false;
}
return true;
}```
```// Efficient Solution : Time Complexity : O(log(min(a,b)))
// a * b = gcd(a,b) * lcm(a,b)

import java.io.*;
import java.util.*;

public class Main {

static int gcd(int a, int b)
{
if(b==0)
return a;

return gcd(b, a % b);
}

static int lcm(int a, int b)
{
return (a * b) / gcd(a, b); // constant no. of operations
}

public static void main (String[] args) {

int a = 4, b = 6;

System.out.println(lcm(a, b));

}
}

// Naive Method : Time Complexity : O(a*b-max(a,b))

static int lcm(int a, int b)
{
int res = Math.max(a,b);

while(res > 0)
{
if(res%a == 0 && res%b == 0)
{
return res;
}
res++;
}
return res;
}```
```// Optimised Euclidean Algorithm Code : Time Complexity : O(log(min(a,b)))

import java.io.*;
import java.util.*;

public class Main {

static int gcd(int a, int b)
{
if(b==0)
return a;

return gcd(b, a % b);
}

public static void main (String[] args) {

int a = 12, b = 15;

System.out.println(gcd(a, b));

}
}

// Euclidean Algorithm Code

static int gcd(int a, int b)
{
while(a!=b)
{
if(a > b)
a = a - b;
else
b = b - a;
}

return a;
}

// Naive Method : Time Complexity : O(min(a,b))

static int gcd(int a, int b)
{
int res = Math.min(a,b);

while(res > 0)
{
if(a%res == 0 && b%res == 0)
{
break;
}
res--;
}

return res;
}```
```// Efficient Method : Time Complexity : Θ(logn), Auxiliary Space: O(1)

import java.io.*;
import java.util.*;

public class Main {

static int countTrailingZeros(int n)
{
int res = 0;

for(int i=5; i<=n; i=i*5)
{
res = res + (n / i);
}

return res;
}

public static void main (String[] args) {

int number = 251;

System.out.println(countTrailingZeros(number));

}
}

// Naive Method : Time Complexity : Θ(n), Auxiliary Space: O(1)

// Overflow for n=20, as factorial value will be of around 19 digits

static int countTrailingZeros(int n)
{
int fact = 1;

for(int i=2; i<=n; i++)
{
fact = fact*i;
}

int res = 0;

while(fact%10 == 0)
{
res++;
fact = fact/10;
}

return res;
}```
```// ITERATIVE CODE : Time Complexity : Θ(n), Auxiliary Space : Θ(1)

import java.io.*;
import java.util.*;

public class Main {

static int fact(int n)
{
int res = 1;

for(int i=2; i<=n; i++)
{
res = res * i;
}
return res;
}

public static void main (String[] args) {

int number = 5;

System.out.println(fact(number));

}
}

// RECURSIVE CODE : Time Complexity : Θ(n), Auxiliary Space : Θ(n)

import java.io.*;
import java.util.*;

public class Main {

static int fact(int n)
{
if(n==0)
return 1;

return n * fact(n-1);
}

public static void main (String[] args) {

int number = 5;

System.out.println(fact(number));

}
}```
```// Time Complexity: O(logN), Auxiliary Space: O(1)
import java.io.*;
import java.util.*;

public class CheckPalindrome {

static boolean isPal(int n)
{
int rev = 0;

int temp = n;
// reversed integer is stored in reversed variable
while(temp != 0)
{
int ld = temp % 10;

rev = rev * 10 + ld;

temp = temp / 10;
}
// palindrome if orignal and reversed are equal
return rev==n;
}

public static void main (String[] args) {

int number = 4553;

System.out.println(isPal(number));

}
}```
```//Time Complexity : O(d), where 'd' is the digits of number
import java.io.*;
import java.util.*;

public class CountDigits {

static int countDigits(int num)
{
int count = 0;

while(num > 0)
{
num = num / 10;
count++;
}
return count;
}

public static void main (String[] args) {

int number = 789;

System.out.println(countDigits(number));

}
}```
```import java.io.*;
import java.util.*;

class Solution
{

public int modInverse(int a, int m)
{
for(int i=1; i<m; i++){
if(a*i%m == 1)
return i;
}
return -1;
}
}

class Main {
public static void main (String[] args) {

//taking input using Scanner class
Scanner sc=new Scanner(System.in);

//taking testcases
int T=sc.nextInt();

while(T-->0)
{
Solution  obj=new Solution ();
int a,m;

//taking input a and m
a=sc.nextInt();
m=sc.nextInt();

//calling function modInverse()
System.out.println(obj.modInverse(a,m));
}

}
}```
```import java.util.*;
import java.lang.*;
import java.io.*;

class Solution
{
static long multiplicationUnderModulo(long a, long b)
{
long M = 1000000007;
return ((a%M)*(b%M))%M;
}
}

class GFG
{
public static void main(String args[])throws IOException
{

//taking testcases

while(t-- > 0)
{

//taking input a and b
long a = Long.parseLong(str[0]);
long b = Long.parseLong(str[1]);

//calling multiplicationUnderModulo() function
System.out.println(new Solution().multiplicationUnderModulo(a, b));
}
}
}```
```import java.io.*;
import java.util.*;

class Solution
{
public static boolean isPrime(int num)
{
if(num==1) return false;
if(num==2 || num==3) return true;
if(num%2==0 || num%3==0) return false;
for(int i=5; i*i<=num; i+=6)
{
if(num%i==0 || num%(i+2)==0)
return false;
}
return true;
}

public static int exactly3Divisors(int N)
{
int count = 0;
for(int i=2; i*i<=N; i++)
{
if(isPrime(i))
count++;
}
return count;
}
}

class Main {
public static void main (String[] args) {
Scanner sc=new Scanner(System.in);

//taking testcases
int T=sc.nextInt();

while(T-->0)
{
Solution obj=new Solution();
int N;
N=sc.nextInt();//taking N
//calling function exactly3Divisors()
System.out.println(obj.exactly3Divisors(N));
}

}
}```
```import java.io.*;
import java.util.*;

class Solution
{

public double termOfGP(int A,int B,int N)
{
// common ratio is given by r=b/a
double r=(double)B/(double)A;
// Nth term is given by a(r^(N-1))
return (A*Math.pow(r,N-1));
}

}

public class Main {
public static void main (String[] args) {

//taking input using Scanner class
Scanner sc=new Scanner(System.in);

//taking total testcases
int T=sc.nextInt();
while(T-->0)
{

Solution  obj=new Solution ();
int A,B;

//taking A and B
A=sc.nextInt();
B=sc.nextInt();
int N;

//taking N
N=sc.nextInt();

//calling method termOfGP() of class GP
System.out.println((int)Math.floor(obj.termOfGP(A,B,N)));

}

}
}```
```import java.io.*;
import java.util.*;

class Solution{
public int digitsInFactorial(int N){

if (N < 0)
return 0;

// base case
if (N <= 1)
return 1;

// else iterate through n and calculate the value
double digits = 0;
for (int i=2; i<=N; i++)
digits += Math.log10(i);

return (int)(Math.floor(digits)) + 1;
}
}

public class Main {
public static void main (String[] args) {
Scanner sc=new Scanner(System.in);

//taking total testcases
int T=sc.nextInt();

while(T-->0)
{
Solution obj=new Solution();
int N;

//taking N
N=sc.nextInt();

//calling method digitsInFactorial()
System.out.println(obj.digitsInFactorial(N));

}

}
}```
```import java.io.*;
import java.util.*;

class Solution {
public ArrayList<Integer> quadraticRoots(int a, int b, int c) {

ArrayList<Integer> numbers = new ArrayList<Integer>();
int d = (int) (Math.pow(b,2)-(4*a*c));
int r1 = (int) Math.floor(((-1*b)+Math.sqrt(d))/(2*a));
int r2 = (int) Math.floor(((-1*b)-Math.sqrt(d))/(2*a));
if(d<0){
}
else
{
}
return numbers;
}
}

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int a, b, c;
a = sc.nextInt();
b = sc.nextInt();
c = sc.nextInt();
Solution obj = new Solution();
ArrayList<Integer> ans = obj.quadraticRoots(a, b, c);
if (ans.size() == 1 && ans.get(0) == -1)
System.out.print("Imaginary");
else
for (Integer val : ans) System.out.print(val + " ");
System.out.println();
}
}
}```
```// Formula	: (0°C × 9/5) + 32 = 32°F

import java.io.*;
import java.util.*;

class Solution
{
public double cToF(int C)
{
return C*(9.0/5.0)+32.0;
}
}

public class Main {
public static void main (String[] args) {
Scanner sc=new Scanner(System.in);

int T=sc.nextInt();//input number of testcases
while(T-->0)
{
Solution obj=new Solution();

int C;
C=sc.nextInt();//input temperature in celscius

System.out.println((int)(obj.cToF(C)));//print the output
}

}
}```
```import java.util.*;
import java.io.*;

class Solution {
public static long sumUnderModulo(long a, long b){

long M = 1000000007;
// a+b mod M = (a mod M + b mod M)mod M
return  (a % M + b % M)%M;
}
}

class GFG
{
public static void main(String args[])throws IOException
{

//taking testcases

while(t-- > 0) {

//taking input a and b
Long a = Long.parseLong(str[0]);
Long b = Long.parseLong(str[1]);

//calling method sumUnderModulo()
System.out.println(new Solution().sumUnderModulo(a,b));
}
}
}```
```import java.io.*;
import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int T = sc.nextInt(); // number of testcases
while (T > 0) {
int I = sc.nextInt();
Solution obj = new Solution();
System.out.println(obj.absolute(I));

T--;
}
}
}

class Solution {
public int absolute(int I) {
int absolute=Math.abs(I);
return absolute;

/*
//used a simple logic

if(I<0){
I=-I;
}
else if(I==0){
I=0;
}
else{
I=I;
}
return I;
*/
}
}```
star

Sun Feb 06 2022 04:24:25 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/primality-test/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #lecture #gfg #geeksforgeeks #efficientmethod #naivemethod #isprime #primalitytest
star

Sun Feb 06 2022 02:48:25 GMT+0000 (UTC) https://practice.geeksforgeeks.org/tracks/DSASP-Mathematics/?batchId=190&tab=2

#java #mathematics #lecture #gfg #geeksforgeeks #factorial #iterative #recursive
star

Sun Feb 06 2022 02:25:06 GMT+0000 (UTC) https://www.geeksforgeeks.org/program-count-digits-integer-3-different-methods/

#java #mathematics #lecture #gfg #geeksforgeeks #countdigits
star

Sun Feb 06 2022 02:13:52 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/modular-multiplicative-inverse-1587115620/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #gfg #geeksforgeeks #modularmultiplicativeinverse
star

Sun Feb 06 2022 02:09:46 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/multiplication-under-modulo/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #gfg #geeksforgeeks #multiplicationundermodulo
star

Sun Feb 06 2022 02:04:54 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/exactly-3-divisors/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #gfg #geeksforgeeks #exactly3divisors
star

Sun Feb 06 2022 01:54:52 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/gp-term/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #gfg #geeksforgeeks #gpterm #geometricprogressionterm #geometricseries
star

Sun Feb 06 2022 01:44:16 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/digits-in-factorial/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #gfg #geeksforgeeks #digitsinfactorial
star

Sun Feb 06 2022 01:36:19 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/quadratic-equation-roots/1/?track=DSASP-Mathematics&batchId=190

star

Sun Feb 06 2022 01:30:39 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/convert-celsius-to-fahrenheit/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #gfg #geeksforgeeks #convertcelsiustofahrenheit
star

Sat Feb 05 2022 12:20:21 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/addition-under-modulo/1/?track=DSASP-Mathematics&batchId=190