Palindrome [Recursive]

 Palindrome [Recursive]

Problem Statement

Palindrome is a word, phrase, or sequence that reads the same backwards as forwards. Use recursion to check if a given string is palindrome or not.

static boolean check_Palindrome(String str,int s, int e) {

     if (str.length() == 0 || str.length() == 1){

            return true;

        } else {

            if (str.charAt(0) != str.charAt(str.length() - 1)){

                return false;

            } else {

                return check_Palindrome(str.substring(1, str.length()-1),s,e);

            }

        }

    }

Multiplication

 Multiplication

Problem Statement

Given two numbers m and n, multiply them using only "addition" operations.

static int  Multiply_by_recursion(int M, int N) 

    { 

      if(N==0)

        return 0;

    return M+Multiply_by_recursion(M,N-1);

  //Enter your code here

    }

Tower of Hanoi

Tower of Hanoi

Problem Statement

From wiki-
The Tower of Hanoi is a mathematical puzzle where we have 3 rods and N disks. The puzzle starts with all the disks in ascending order of size on the first row. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
3. No larger disk may be placed on top of a smaller disk.
-----x--x--x------

 import java.io.*; // for handling input/output

import java.util.*; // contains Collections framework

// don't change the name of this class

// you can add inner classes if needed

class Main {

    

static void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) 

    { 

        if (n == 1) 

        { 

            System.out.println("1:" +  from_rod + "->" + to_rod); 

            return; 

        } 

        towerOfHanoi(n-1, from_rod, aux_rod, to_rod); 

        System.out.println(n + ":" +  from_rod + "->" + to_rod); 

        towerOfHanoi(n-1, aux_rod, to_rod, from_rod); 

    } 

      

    //  Driver method 

    public static void main(String args[]) 

    { Scanner sc=new Scanner(System.in);

        int n = sc.nextInt();

        towerOfHanoi(n, 'A', 'C', 'B');  // A, B and C are names of rods 

    } 

}

Boundary Traversal of Matrix

Boundary Traversal of Matrix

Problem Statement

You are given a matrix A of dimensions n x m. The task is to perform boundary traversal on the matrix in clockwise manner.

import java.io.*; // for handling input/output

import java.util.*; // contains Collections framework

// don't change the name of this class

// you can add inner classes if needed

class Main {

    public static void main (String[] args) {

   Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        

        while(t-- > 0)

        {

            int n1 = sc.nextInt();

            int m1 = sc.nextInt();

            

            int arr1[][] = new int[n1][m1];

            

            for(int i = 0; i < n1; i++)

            {

                for(int j = 0; j < m1; j++)

                 arr1[i][j] = sc.nextInt();

            }

            boundaryTraversal(n1, m1,arr1);

            System.out.println();

            

        }

    }

static void boundaryTraversal( int n1, int m1, int arr1[][])

    {

        // base cases

        if(n1 == 1)

        {

            int i = 0;

            while(i < m1)

            System.out.print(arr1[0][i++] + " ");

        }

        else if(m1 == 1)

        {

            int i = 0;

            while(i < n1)

            System.out.print(arr1[i++][0]+" ");

        }

        else

        {

            

            // traversing the first row

            for(int j=0;j<m1;j++)

            {

                System.out.print(arr1[0][j]+" ");

            }

            

            // traversing the last column

            for(int j=1;j<n1;j++)

            {

                System.out.print(arr1[j][m1-1]+ " ");

            }

            

            // traversing the last row

            for(int j=m1-2;j>=0;j--)

            {

                System.out.print(arr1[n1-1][j]+" ");

            }

            

            // traversing the first column

            for(int j=n1-2;j>=1;j--)

            {

               System.out.print(arr1[j][0]+" ");

            }

            

        } 

            

    }

}

Simple-Transpose

 Simple-Transpose

Problem Statement

You are given a NxN matrix. You need to find the transpose of the matrix.
The matrix is of form:
a b c ...
d e f ...
g h i ...
...........
There are N elements in each row.

import java.io.*; // for handling input/output

import java.util.*; // contains Collections framework

// don't change the name of this class

// you can add inner classes if needed

class Main {

    public static void main (String[] args) {

                      // Your code here

        Scanner sc= new Scanner(System.in);

        int n = sc.nextInt();

        int arr[][] = new int[n][n];

        for(int i=0;i<n;i++)

        {

            for (int j=0;j<n;j++)

            {

                arr[i][j]=sc.nextInt();

                

            }

        }

        for(int i=0;i<n;i++)

        {

            for (int j=0;j<n;j++)

            {System.out.print(arr[j][i] + " ");

    }System.out.println();

}

    }

}

Simple-Determinant

 Simple-Determinant

Problem Statement

You are given a 2X2 square matrix. You need to find the determinant of the matrix.

import java.io.*; // for handling input/output

import java.util.*; // contains Collections framework

// don't change the name of this class

// you can add inner classes if needed

class Main {

    public static void main (String[] args) {

                      // Your code here

        Scanner sc = new Scanner(System.in);

    int a[][]=new int[2][2];

    for(int i=0;i<2;i++)

    {

        for(int j=0;j<2;j++)

        {

            a[i][j]=sc.nextInt();

            

        }

    }System.out.println((a[0][0] * a[1][1]) - (a[0][1] * a[1][0]));

    }}

Walter White Easy

 Walter White Easy

Problem Statement

Walter white is considered very intelligent person. He has a problem to solve. As he is suffering from cancer, can you help him solve it?
Given two integer arrays C and S of length c and s respectively. Index i of array S can be considered good if a subarray of length c can be formed starting from index i which is complimentary to array C.
Two arrays A, B of same length are considered complimentary if any cyclic permutation of A satisfies the property (A[i]- A[i-1]=B[i]-B[i-1]) for all i from 2 to length of A (1 indexing).
Calculate number of good positions in S .
Cyclic Permutation
1 2 3 4 has 4 cyclic permutations 2 3 4 1, 3 4 1 2, 4 1 2 3,1 2 3 4

#include<bits/stdc++.h>

using namespace std;

#define pu push_back

#define fi first

#define se second

#define mp make_pair

// #define int long long

#define pii pair<int,int>

#define mm (s+e)/2

#define all(x) x.begin(), x.end()

#define For(i, st, en) for(int i=st; i<en; i++)

#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)

#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);

#define sz 2000015

#define qw1 freopen("input1.txt", "r", stdin); freopen("output1.txt", "w", stdout);

#define qw2 freopen("input2.txt", "r", stdin); freopen("output2.txt", "w", stdout);

#define qw3 freopen("input3.txt", "r", stdin); freopen("output3.txt", "w", stdout);

#define qw4 freopen("input4.txt", "r", stdin); freopen("output4.txt", "w", stdout);

#define qw5 freopen("input5.txt", "r", stdin); freopen("output5.txt", "w", stdout);

#define qw6 freopen("input6.txt", "r", stdin); freopen("output6.txt", "w", stdout);

#define qw freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

#define sajid main

int A[sz],B[sz],C[sz],D[sz],E[sz],F[sz],G[sz];

int n,m;

signed sajid()

{

    

        

        cin>>n;

        for(int i=0;i<n;i++)

        {

            cin>>A[i];

            F[i]=A[i];

        }

        cin>>m;

        for(int i=0;i<m;i++)

        {

            cin>>B[i];

            G[i]=B[i];

            C[m-i-1]=B[i];

        }

        C[m]=-500000000;

        for(int i=0;i<n;i++)

        {

            C[i+m+1]=A[n-i-1];

        }

       int l=0,r=0;

       for(int i=1;i<=n+m;i++)

        {

            if(i<=r)

            {

                E[i]=min(r-i+1,E[i-l]);

            }

            while(i+E[i]<=n+m && C[E[i]]-C[0]==C[i+E[i]]-C[i])

             E[i]++;

 

            if(i+E[i]-1>r) {

                l=i;r=i+E[i]-1;

            }

        }

       for(int i=0;i<m;i++)

       {

        C[i]=B[i];

       }

       for(int i=0;i<n;i++)

       {

        C[i+m+1]=A[i];

       }

       for(int i=0;i<n;i++)

       {

          A[i]=E[n+m-i];

       }

        l=0;

        r=0;

        for(int i=1;i<=n+m;i++)

        {

            if(i<=r)

            {

                D[i]=min(r-i+1,D[i-l]);

            }

            while(i+D[i]<=n+m && C[D[i]]-C[0]==C[i+D[i]]-C[i])

             D[i]++;

            if(i+D[i]-1>r) {

                l=i;r=i+D[i]-1;

            }

        }

        // cout<<0<<" ";

        for(int i=0;i<n;i++)

        {

            B[i]=D[i+m+1];

            

        }

       

        int cnt=0;

        vector<pii> xx,yy;

          for(int i=0;i<=n;i++){

            int a=0;

            int b=0;

            if(i>0) a=A[i-1];

            if(i<n) b=B[i];

            // cout<<i<<" "<<a<<" "<<b<<endl;

           if(a+b>=m && (a==0 || b==0 ||(F[i]-F[i-1]==G[0]-G[m-1]))) 

                {xx.pu(mp(i-a,i+b-m));  }

            if(a==m) xx.pu(mp(i-a,i-a));

              if(b==m ) xx.pu(mp(i,i));

           

        }

        sort(xx.begin(),xx.end());

        for(int i=0;i<xx.size();i++)

        {  

            if(yy.size()==0) yy.pu(mp(xx[i].fi,xx[i].se));

            else{

                int p=yy.size()-1;

                

                if(yy[p].se>=xx[i].se) continue;

                if(yy[p].se>=xx[i].fi) yy[p].se=xx[i].se;

                else yy.pu(mp(xx[i].fi,xx[i].se));

            }

        }

        for(int i=0;i<yy.size();i++)

        { 

            cnt+=yy[i].se-yy[i].fi+1;

        }

        cout<<cnt<<endl;

    

}

Pair Em Up (Contest)

 Pair Em Up (Contest)

Problem Statement

Given an array of N elements where N is even. You have to pair up the elements into N/2 pairs such that each element is in exactly 1 pair. You need to find minimum possible X such that there exists a way to pair the N elements and for no pair sum of its elements is greater than X.

import java.io.*; // for handling input/output

import java.util.*; // contains Collections framework

class Main{

public static void main(String args[]){

int n;

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();

        int a[] = new int[n];

        for(int i=0;i<n;i++) {

            a[i] = sc.nextInt();

        }

        Arrays.sort(a);

        int maxi = -1;

        for(int i=0; i<n; i++) {

            int cur = a[i] + a[n-i-1];

            if(maxi<cur)

                maxi = cur;

        }

        System.out.println(maxi);

        }

}

NoXor (Simple Contest)

 NoXor (Simple Contest)

Problem Statement

We need a problem on xor again. Given an array A of N integers (1- indexed), you need to find the sum of (N- i) xor A[i] for all i from 1 to N

import java.io.*; 

import java.util.*;

class Main 

{

    public static void main (String[] args) 

    {

        Scanner sc=new Scanner(System.in);

        int N=sc.nextInt();

        if(N>0)

        {

        int A[]=new int[N];

        for(int i=0;i<N;i++)

        {

            A[i]=sc.nextInt();

        }

        long sum=0;

                    

        for(int i=1;i<=N;i++)

        {

            

            

            int P=(N-i)^A[(i-1)];

            sum=sum+P;

            

        }

        System.out.println(sum);

    }

}

}

Mohit and array

 Mohit and array

Problem Statement

Mohit has an array of N integers containing all elements from 1 to N, somehow he lost one element from the array.
Given N-1 elements your task is to find the missing one.

import java.io.*; // for handling input/output

import java.util.*; // contains Collections framework

// don't change the name of this class

// you can add inner classes if needed

class Main {

    public static void main (String[] args) {

                      // Your code here

        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();

        int arr[] = new int[n];

        

        

        for(int i=0;i<n-1;i++)

        {

            arr[i] = scan.nextInt();

        }

        int sum = n*(n+1)/2;

        int total = 0;

        for(int i=0;i<n-1;i++)

        {

            //arr[i] = scan.nextInt();

            total = total + arr[i];

        }

        int b = sum - total;

        

        System.out.println(b);

    }

    

}

Maximum and Minimum in an Array

 Maximum and Minimum in an Array

Problem Statement

Given an array A[ ] of size N containing positive integers, find maximum and minimum elements from the array.

import java.io.*; // for handling input/output

import java.util.*; // contains Collections framework

// don't change the name of this class

// you can add inner classes if needed

class Main {

    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int testcase = sc.nextInt();

        while (testcase>0){

            int n =sc.nextInt();

            int arr[]=new int[n];

        for (int i=0;i<n;i++){

             arr[i]=sc.nextInt();

        }

        int mini = arr[0];

        int maxi = arr[0];

        for(int i=1;i<n;i++){

            if(mini>arr[i]){

                mini = arr[i];

            }

            if (maxi<arr[i]){

                maxi=arr[i];

           }

        }

           System.out.println(maxi+" "+mini);

     testcase--;

    

}

    }

}

Hip Hip Array

 Hip Hip Array

Problem Statement

You will be given an array of N numbers. Your task is to first reverse the array (first number becomes last, 2nd number becomes 2nd from the last and so on) and then print the sum of the numbers at even indices and print the product of the numbers at odd indices.

import java.io.*; // for handling input/output

import java.util.*; // contains Collections framework

// don't change the name of this class

// you can add inner classes if needed

class Main 

{

    public static void main (String[] args) 

    {

     Scanner sc=new Scanner(System.in);

     int sum=0;

     long product=1;

     int N=sc.nextInt();

     if(N>0)

     {

     int arr[]=new int[N];

     //array to store new elements

     int arr1[]=new int[N];

     for(int i=0;i<N;i++)

     {

         arr[i]=sc.nextInt();

     }

     for(int i=0;i<N;i++)

     {

         arr1[i]=arr[(N-1)-i];

     }

     for(int i=1;i<N;i+=2)

     {

         sum=sum+arr1[i];

     }

        System.out.print(sum+" ");

    for(int i=0;i<N;i+=2)

    {

        product=product*arr1[i];

    }

    System.out.print(product);

     

    }

}}

Buildings

 Buildings

Problem Statement

There are N buildings in a row with different heights H[i] (1 <= i <= N).
You are viewing the buildings from the left and you can see the roof of a building i if no building to the left of the ith building has a height greater than the ith building.
You are asked to find the number of buildings whose roofs you can see.

import java.io.*; 

import java.util.*; 

class Main {

    public static void main (String[] args) {

    Scanner sc = new Scanner(System.in);

        int buld=sc.nextInt();

        int a[]=new int[buld];

        for(int i=0;i<buld;i++){

            a[i]=sc.nextInt();

        }

        int count=1;

        int max=a[0];

        for(int i=1;i<buld;i++){

            

                if(max<a[i]){

                    ++count;

                    max=a[i];

                }

        }

       System.out.print(count);

    }

}

Maximum difference array

 Maximum difference array

Problem Statement

Given an array of integers of size N, your task is to find the maximum parity index of this array.
Parity Index is the maximum difference between two indices i and j (1 <= i <= j <= N) of an array A such that Ai < Aj.

import java.io.*; // for handling input/output

import java.util.*; // contains Collections framework

// don't change the name of this class

// you can add inner classes if needed

class Main

{

public static void main (String[] args) {

        // Your code here

        Scanner scan = new Scanner(System.in);

        int maxDiff = -1;

        int n = scan.nextInt();

        int[] arr = new int[n];

        for(int i = 0; i < n; i++){

          arr[i] = scan.nextInt();

        }

        int []rightMax = new int[n];

        rightMax[n-1]= arr[n-1];

        for(int i = n-2; i>=0; i--)

          rightMax[i] = Math.max(rightMax[i+1] , arr[i]);

    

        int maxDist = Integer.MIN_VALUE;

        int i = 0, j = 0;

        while(i < n && j < n)

        {

          if(rightMax[j] > arr[i])

          {

            maxDist = Math.max( maxDist, j-i );

            j++;

          }

          else

            i++;

        }

      System.out.println(maxDist);

  }

}

Max numbers

 Max numbers

Problem Statement

Given an array A of size N, you need to find its maximum, 2nd maximum and 3rd maximum element.

import java.io.*; // for handling input/output

import java.util.*; // contains Collections framework

// don't change the name of this class

// you can add inner classes if needed

class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());

        while (t-->0) {

            int n = Integer.parseInt(br.readLine());

            int max, max2, max3;

            max3 = max = max2 = -1;

            int x = 0;

             String srr[] = br.readLine().trim().split(" ");

            for (int i = 0; i < n; i++) {

                x =Integer.parseInt(srr[i]);

                if (x > max) {

                    max3 = max2;

                    max2 = max;

                    max = x;

                } else if (x > max2) {

                    max3 = max2;

                    max2 = x;

                } else if (x > max3)

                    max3 = x;

            }

            System.out.println(max + " " + max2 + " " + max3);

            

        }}}