Snippets Collections
// 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
    {
        
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        
        //taking testcases
        int t = Integer.parseInt(read.readLine());
        
        while(t-- > 0)
        {
            String str[] = read.readLine().trim().split(" ");
            
            //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){
           numbers.add(-1);
       }
       else
       {
           numbers.add(Math.max(r1,r2));
           numbers.add(Math.min(r1,r2));
       }
       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
    {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        
        //taking testcases
        int t = Integer.parseInt(read.readLine());
        
        while(t-- > 0) {
            String[] str = read.readLine().trim().split(" ");
            
            //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 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/quadratic-equation-roots/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #gfg #geeksforgeeks #quadraticequationroots
star

Sun Feb 06 2022 01:30:39 GMT+0000 (Coordinated Universal Time) 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 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/addition-under-modulo/1/?track=DSASP-Mathematics&batchId=190

#java #additionundermodulo #mathematics #gfg #geeksforgeeks
star

Sat Feb 05 2022 12:16:24 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/absolute-value/1/?track=DSASP-Mathematics&batchId=190

#java #absolutevalue #mathematics #gfg #geeksforgeeks

Save snippets that work with our extensions

Available in the Chrome Web Store Get Firefox Add-on Get VS Code extension