Count duplicates(Hashing)

 Count duplicates(Hashing)

Problem Statement

Given an array of N elements, your task is to find the count of repeated elements. Print the repeated elements in ascending order along with their frequency.
Have a look at the example for more understanding.

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 inputTaker = new Scanner(System.in);

        int n = inputTaker.nextInt();

        int[] arr = new int[n];

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

            arr[i] = inputTaker.nextInt();

        }

        HashMap<Integer, Integer> map = new HashMap<>();

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

            if (map.containsKey(arr[i])) {

                Integer prevCount = map.get(arr[i]);

                map.put(arr[i], prevCount + 1);

            } else {

                map.put(arr[i], 1);

            }

        }

        for (Integer number : map.keySet()) {

            if (map.get(number) > 1) {

                System.out.println(number + " " + map.get(number));

            }

        }

    }

}

Unique number of characters(Hashing)

 Unique number of characters(Hashing)

Problem Statement

Given a string s, your task is to find the total number of unique characters in a string.

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);

        HashSet<Character> hs = new HashSet<>();

        String str = sc.nextLine();

        int n = str.length();

        for(int i=0;i<n;i++){ //pick char by char 

            hs.add(str.charAt(i));

        }

        System.out.println(hs.size());

    }

}

Largest subarray with zero sum(Hashing)

 Largest subarray with zero sum(Hashing)

Problem Statement

Given an array A[], of length N containing values in the range of negative to positive integers. You need to find the length of the largest subarray whose sum of elements is 0.

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 int maxLen(int arr[], int n) {

        HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();

        int sum = 0;

        int max_len = 0;

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

            sum += arr[i];

            if (arr[i] == 0 && max_len == 0) {

                max_len = 1;

            }

            if (sum == 0) {

                max_len = i + 1;

            }

            Integer prev_i = hM.get(sum);

            if (prev_i != null) {

                max_len = Math.max(max_len, i - prev_i);

            } else {

                hM.put(sum, i);

            }

        }

        return max_len;

    }

    public static void main(String[] args) {

        // Your code here

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] arr = new int[n];

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

            arr[i] = sc.nextInt();

        }

        int nn = maxLen(arr, n);

        if (nn > 0) {

            System.out.println(nn);

        } else {

            System.out.println("-1");

        }

    }

}

Distinct Vals (Hashing)

 Distinct Vals (Hashing)

Problem Statement

Given an array Arr of N elements. Find the minimum number of elements that you need to delete from this array such that all the elements in the array become distinct.

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 n=sc.nextInt();

HashSet<Integer> hs=new HashSet<>();

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

{

    int num=sc.nextInt();

    hs.add(num);

}

System.out.print(n-hs.size()+" ");

    }

}

Travelling

 Travelling

Problem Statement

Given N cities in a line and your initial position, you want to visit all the cities at least once. You can go to one coordinate P to P+D or P-D where D is the number of steps which you choose initially. Your task is to find the maximum value of D such that you can visit all the cities at least once.

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 scn = new Scanner(System.in);

        int n = scn.nextInt();

        int x = scn.nextInt();

        int[] city = new int[n];

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

            city[i] = Math.abs(scn.nextInt()-x);

        }

        //now solve the problem

        int gcd_=gcd(city[0],city[1]);

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

            gcd_= gcd(gcd_,city[i]);

        }

        System.out.println(gcd_);

    }

    //method to find gcd

    static int gcd(int m, int n){

        if(m==0){

            return n;

        }

        if(n==0){

            return m;

        }

        if(m==n){

            return m;

        }

        if(m>n){

            return gcd(m%n, n);

        }

        return gcd(n%m, m);

    }

}

Closest Buddy (Contest)

Closest Buddy (Contest)

 Problem Statement

You are given an integer array A of size N. For each index i (1 <= i <= N), you need to find an index j, such that gcd(A[i], A[j]) = 1, and abs(i-j) is the minimum possible. If there are two values of j satisfying the condition, report the minimum one. If there is no possible value of j, report -1.

Note: gcd(x, y) represents the the greatest common divisor of integers x and y, while abs(i- j) represents the absolute value of (i-j). Eg: gcd(6, 15) = 3 ; abs(6-15) = 9.

#include <bits/stdc++.h>

 using namespace std;

 #define sd(x) scanf("%d", &x)

 #define sz(v) (int) v.size()

 #define pr(v) For(i, 0, sz(v)) {cout<<v[i]<<" ";} cout<<endl;

 #define slld(x) scanf("%lld", &x)

 #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 pb push_back

 #define sajid_pathan main

 #define ll long long

 #define ld long double

 #define double long double

 #define mp make_pair

 #define F first

 #define S second

 typedef pair<int, int> pii;

 typedef vector<int> vi;

 #define pi 3.141592653589793238

 const int MOD = 1e9+7;

 

 

 const int N = 2e5+5;

 

 

 

 int pre[N][55], suf[N][55];

 int arr[N];

 

 void solve(){

     int n; cin>>n;

     For(i, 1, n+1){

         cin>>arr[i];

     }

     For(i, 1, n+1){

         For(j, 1, 51){

             if(arr[i]==j)

                 pre[i][j]=i;

             else

                 pre[i][j]=pre[i-1][j];

         }

     }

     for(int i=n; i>=1; i--){

         For(j, 1, 51){

             if(arr[i]==j){

                 suf[i][j]=i;

             }

             else{

                 suf[i][j]=suf[i+1][j];

             }

         }

     }

     vector<int> ans(n+1, -1);

     For(i, 1, n+1){

         int dist = 3e5;

         For(j, 1, 51){

             if(__gcd(arr[i], j)==1){

                 if(pre[i][j] && abs(i-pre[i][j])<=dist){

                     ans[i]=pre[i][j];

                     dist=abs(i-pre[i][j]);

                 }

                 if(suf[i][j] && abs(i-suf[i][j])<dist){

                     ans[i]=suf[i][j];

                     dist=abs(i-suf[i][j]);

                 }

             }

         }

     }

     set<int> s;

     For(i, 1, n+1){

         s.insert(ans[i]);

         cout<<ans[i]<<" ";

     }

 }

 

 

 signed sajid_pathan()

 {

         solve();

 }

GCD Pairs (Contest)

 GCD Pairs (Contest)

Problem Statement

Given an array Arr of N elements. Find the maximum value of GCD(Arr[i], Arr[j]) where i != j.

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 int findMaxGCD(int arr[], int n)

    {

        int high = 0;

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

            high = Math.max(high, arr[i]);

      

        int divisors[] =new int[high + 1];

      

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

        {

            for (int j = 1; j <= Math.sqrt(arr[i]); j++)

            {

                if (arr[i] % j == 0)

                {

                    divisors[j]++;

      

                    if (j != arr[i] / j)

                        divisors[arr[i] / j]++;

                }

            }

        }

      

        for (int i = high; i >= 1; i--)

            if (divisors[i] > 1)

                return i;

        return 1;

    }

    public static void main (String[] args) {

                      // Your code here

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int arr[] = new int[n];

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

            arr[i] = sc.nextInt();

        }

        System.out.print(findMaxGCD(arr,n));

    }

}

Area of Square - JAVA PROGRAM

Area of Square 

Problem Statement

Given a side of a square, your task is to calculate its area. Input The first line of the input contains the side of the square.

Constraints: 1 <= side <=100 

Output You just have to print the area of a square

Example Sample Input:- 3

 Sample Output:- 9 

 Sample Input:- 6 

 Sample Output:- 36

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 a = sc.nextInt();

 System.out.println(a*a);

    }

}