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

    }

}

Identical Groups

 Identical Groups

Problem Statement

Myra has x red colour balls and y blue colour balls. She wants to distribute these balls into identical groups without any balls left. What is the largest number of groups she can make?

Identical groups mean there are equal number of same coloured balls in each group.

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

        int yBlue=sc.nextInt();

        int min=xRed>yBlue?yBlue:xRed;

        int count=0;

     

        System.out.println(gcd(xRed,yBlue));

    }

    static int gcd(int a, int b)

    {

    if (b == 0)

        return a;

        

    return gcd(b, a % b);

    }

}

GCD frequency

 GCD frequency

Problem Statement

Given an integer array A of size N. Find the sum of GCD (Greatest Common Divisor) of all elements with their frequency.

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 gcd(int a, int b){

        if(b==0) return  a;

        return gcd(b, a%b);

    }

    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int arr[] = new int[n];

        int freq[] = new int[100001];

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

            int num = sc.nextInt();

            arr[i] = num;

            freq[num] = freq[num]+1;

        }

        long sum = 0;

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

            sum = sum + gcd(arr[i], freq[arr[i]]);

        }

        System.out.println(sum);

    }

}

Is this prime?

 Is this prime?

Problem Statement

Let's assume some functional definitions for this problem.
We take prime(x) as the set of all prime divisors of x. For example, prime(140)={2,5,7}, prime(169)={13}.

Let f(x,p) be the maximum possible integer p**k where k is an integer such that x is divisible by p**k.
(Here a**b means a raised to the power b or pow(a, b))
For example:
f(99,3)=9 (99 is divisible by 3**2=9 but not divisible by 3**3=27),
f(63,7)=7 (63 is divisible by 7**1=7 but not divisible by 7**2=49).

Let g(x,y) be the product of f(y,p) for all p in prime(x).
For example:
g(30,70)=f(70,2)*f(70,3)*f(70,5)=2*1*5=10,
g(525,63)=f(63,3)*f(63,5)*f(63,7)=9*1*7=63.

You are given two integers x and n. Calculate g(x,1)*g(x,2)*…*g(x,n) mod (1000000007).

c++ code:

#include<bits/stdc++.h>

#pragma GCC optimize "03"

using namespace std;

#define Sajid main

#define int long long int

#define ld long double

#define pi pair<int, int>

#define pb push_back

#define fi first

#define se second

#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

#ifndef LOCAL

#define endl '\n'

#endif

 

const int N = 2e5 + 5;

const int mod = 1e9 + 7;

const int inf = 1e9 + 9;

int power(int a, int b){

    int ans = 1;

    b %= (mod-1);

    while(b){

        if(b&1)

            ans = (ans*a) % mod;

        b >>= 1;

        a = (a*a) % mod;

    }

    return ans;

}

int f(int n, int p){

    int ans = 1;

    int cur = 1;

    while(cur <= n/p){

        cur = cur*p;

        int z = power(p, n/cur);

        ans = (ans*z) % mod;

    }

    return ans;

}

signed Sajid() {

    IOS;

    int x, n, ans = 1;

    cin >> x >> n;

    for(int i = 2; i*i <= x; i++){

        if(x%i != 0)    continue;

        ans = (ans*f(n, i)) % mod;

        while(x%i == 0)

            x /= i;

    }   

    if(x > 1)

        ans = (ans*f(n, x)) % mod;

    cout << ans;

    return 0;

}