ARRAYS

simple and Complex problems in arrays are given with the solution

1) Find the longest bitonic sub-sequence length of the given array

import java.util.*;
  
public class Main
{ 
    static int LBS( int arr[], int n ) 
    { 
        int[] LIS = new int[n]; 
        for (int index = 0; index < n; index++)
        {
            LIS[index] = 1; 
        }
        
        for (int index1 = 1; index1 < n; index1++) 
        {
            for (int index2 = 0; index2 < index1; index2++)
            {
                if(arr[index1]>arr[index2] && LIS[index1] < LIS[index2] + 1) 
                {
                    LIS[index1] = LIS[index2] + 1; 
                }
            }
        }
  
        int[] LDS = new int [n]; 
        for (int index = 0; index < n; index++) 
        {
            LDS[index] = 1; 
        }

        for (int index1 = n-2; index1 >= 0; index1--) 
        {
            for (int index2 = n-1; index2 > index1; index2--)
            {
                if(arr[index1]>arr[index2] && LDS[index1] < LDS[index2] + 1)
                {
                    LDS[index1] = LDS[index2] + 1; 
                }
            }
        }
  
        int max = LIS[0] + LDS[0] - 1; 
        for (int index = 1; index < n; index++) 
        {
            if (LIS[index] + LDS[index] - 1 > max) 
                max = LIS[index] + LDS[index] - 1; 
        }
  
        return max; 
    } 
  
    public static void main (String[] args) 
    { 
        Scanner sc=new Scanner(System.in);
        int size=sc.nextInt();
        int arr[] = new int[size];
        for(int index=0;index<size;index++)
        {
            arr[index]=sc.nextInt();
        }
        System.out.println("The Length of Longest Bitonic Subsequence in the given array is : "+ LBS( arr, size )); 
    } 
} 

input 1:
16
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

output 1:
The Length of Longest Bitonic Subsequence in the given array is : 7

input 2:
6
80 60 30 40 20 10

output 2:
The Length of Longest Bitonic Subsequence in the given array is : 5
2) array left rotation with O(n) time complexity
import java.util.*;

public class Main{
  public static void main (String[] args) {
   sc=new Scanner(System.in);
      int size=sc.nextInt();
      int k=sc.nextInt();
      int[] arr=new int[size];
      for(int index1=0;index1<size;index1++)
      {
          arr[index1]=sc.nextInt();
      }
       int mod=k%size;
          for(int index1=0;index1<size;index1++)
          {
              System.out.print(arr[(index1+mod)%size]+" ");
          }
 }
}

input 1:
5 2
1 2 3 4 5

output 1:
3 4 5 1 2

input 2:
8 4
1 2 3 4 5 6 7 8

output 2:
5 6 7 8 1 2 3 4
Find the Array Leaders

import java.util.*;
public class MyClass 
{
    public static void main(String args[]) 
    {
        Scanner sc=new Scanner(System.in);
        List<Integer> al=new ArrayList<>();
        while(sc.hasNext())
        {
            al.add(sc.nextInt());
        }
        int l=al.size();
        for(int i=0;i<l;i++)
        {
            int j=0;
            for(j=i+1;j<l;j++)
            {
                if(al.get(i)<=al.get(j))
                {
                    break;
                }
            }
            if(j==l)
            System.out.print(al.get(i)+" ");
        }
    }
}

input:
10 17 5 3 4 2

output:
17 5 2
Sort array based on factor count

import java.util.*; 
public class Main
{ 
    int index, factors; 
    public Main(int i, int countFactors) 
    { 
        index = i; 
        factors = countFactors; 
    } 
    static int countFactors(int n)
    {
        int count=0;
        for(int index=1;index<=n;index++)
        {
            if(n%index==0)
            count++;
        }
        return count;
    }
    static void print(int arr[], int n) 
    {     
        Main num[] = new Main[n];
        for (int i=0; i<n; i++) 
        { 
            num[i] = new Main(i,countFactors(arr[i])); 
        } 
        Arrays.sort(num,new Comparator<Main>() { 
            @Override
            public int compare(Main e1, Main e2) 
            { 
                if (e1.factors == e2.factors) 
                 return e1.index < e2.index ? -1 : 1; 
                return e1.factors > e2.factors ? -1 : 1;   
            } 
        }); 
        for (int i=0; i<n; i++) 
        {
            System.out.print(arr[num[i].index]+" "); 
        }
    } 
    public static void main(String[] args)  
    { 
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int index=0;index<n;index++)
        {
            arr[index]=sc.nextInt();
        }
        print(arr,n); 
  
    } 
}

input 1:
7                                                             
5 11 10 20 9 16 23  

output 1:
20 16 10 9 5 11 23

explanation:
sort the elements based on the factor count. if tow or more elements have the same factor count, then sort them based on the occurence of index in the array
Rearrange an array by placing +ve and -ve integers alternatively

import java.util.*;
public class Main
{
    public static int partition(int[] arr)
    {
        int index2=0;
        int pivot=0;
        for(int index=0;index<arr.length;index++)
        {
            if(arr[index]<pivot)
            {
                int temp=arr[index];
                arr[index]=arr[index2];
                arr[index2]=temp;
                index2++;
            }
        }
        return index2;
    }
    public static void rearrange(int[] arr)
    {
        int p=partition(arr);
        for(int index=0;p<arr.length&&index<p;p++,index+=2)
        {
            int temp=arr[index];
            arr[index]=arr[p];
            arr[p]=temp;
        }
    }
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int index=0;index<n;index++)
        {
            arr[index]=sc.nextInt();
        }
        rearrange(arr);
        for(int index=0;index<arr.length;index++)
        {
            System.out.print(arr[index]+" ");
        }
    }
}

Input 1:
8
9  -3  5  -2  -8  -6  1  3
Output 1:
5 -2 9 -6 1 -8 3 -3
Maximum Path sum in two arrays

import java.util.*;
public class Main 
{ 
    static int maxPathSum(int ar1[], int ar2[], int m, int n)  
    { 
        int i = 0, j = 0; 
        int result = 0, sum1 = 0, sum2 = 0; 
        while (i < m && j < n)  
        { 
            if (ar1[i] < ar2[j]) 
                sum1 += ar1[i++]; 
            else if (ar1[i] > ar2[j]) 
                sum2 += ar2[j++]; 
            else
            { 
                result += Math.max(sum1, sum2);
                sum1 = 0; 
                sum2 = 0; 
                while (i < m && j < n && ar1[i] == ar2[j])  
                { 
                    result = result + ar1[i++]; 
                    j++; 
                } 
            } 
        } 
        while (i < m) 
            sum1 += ar1[i++];
        while (j < n)  
            sum2 += ar2[j++]; 
        result += Math.max(sum1, sum2); 
        return result; 
    } 
    public static void main(String[] args)  
    { 
        Scanner sc=new Scanner(System.in);
        int M=sc.nextInt();
        int arr1[]=new int[M];
        for(int index=0;index<M;index++)
        {
            arr1[index]=sc.nextInt();
        }
        int N=sc.nextInt();
        int arr2[]=new int[N];
        for(int index=0;index<N;index++)
        {
            arr2[index]=sc.nextInt();
        }
        System.out.println("Maximum sum path is :" + maxPathSum(arr1, arr2, M, N)); 
    } 
}

input 1:
6
1 5 10 15 20 25
5
2 4 5 9 15

output 1:
Maximum sum path is : 81
Find the Array Leaders 

import java.util.*;
public class Main  
{ 
    static void printLeaders(int arr[], int size)  
    { 
        for (int index1 = 0; index1 < size; index1++)  
        { 
            int index2; 
            for (index2 = index1 + 1; index2 < size; index2++)  
            { 
                if (arr[index1] <= arr[index2]) 
                    break; 
            } 
            if (index2 == size) 
                System.out.print(arr[index1] + " "); 
        } 
    } 
    public static void main(String[] args)  
    { 
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int[] arr=new int[N];
        for(int index=0;index<N;index++)
        {
            arr[index]=sc.nextInt();
        }
        printLeaders(arr, N); 
    } 
}

input 1:
6
16 17 4 3 5 2

output 1:
17 5 2

explanation:
the elements that are greater than the current element to its right are said to as array leaders.
Find array element sum

import java.util.*;
public class Main
{
    public static void main(String args[]) 
    {
        Scanner sc=new Scanner(System.in);
    int N=sc.nextInt();
    int arr[]=new int[N];
    for(int index=0;index<N;index++)
    {
        arr[index]=sc.nextInt();
    }
    int start=0,end=N-1;
    while(start<end)
    {
        System.out.print(arr[start]+arr[end]+" ");
        start++;
        end--;
    }
    if(N%2==1)
    {
        System.out.print(arr[N/2]);
    }
}
}

input 1:
5
12 3 4 5 8

output 2:
20 8 4

explanation:
print the sum of first and Nth element,then second element and N-1th element, and so on... if N is odd, print the middle element 
 
input 2:
8
9 8 2 1 10 2 3 7

output 2:
16 11 4 11 
Find Array2 is a mirror of Array1 

import java.util.*;
public class Main {

    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr1=new int[n];
        int[] arr2=new int[n];
        for(int index=0;index<n;index++)
        {
            arr1[index]=sc.nextInt();
        }
        for(int index=0;index<n;index++)
        {
            arr2[index]=sc.nextInt();
        }
        int end=n-1,flag=0;
        for(int index=0;index<n;index++)
        {
            if(arr1[index]==arr2[end])
            {
                flag++;
            }
            end--;
        }
        if(flag==n)
        System.out.print("1");
        else
        System.out.print("0");
  }
}

input 1:
4                                                                                                                               
10 20 30 40                                                                                                                     
40 30 20 10

output 1:
1 

input 2:
5                                                                                                                             
10 20 30 40 50                                                                                                                
50 30 20 40 10  

output 2:
0
Find missing integers in the given range:

import java.util.*;
public class Main 
{ 
    static void printMissing(int arr[], int low, int high) 
    {
        boolean[] points = new boolean[high - low + 1];
        for (int i = 0; i < arr.length; i++) 
        {
            if (low <= arr[i] && arr[i] <= high) 
            {
                points[arr[i] - low] = true;
            }
        } 
        for (int x = 0; x <= high - low; x++) 
        { 
            if (points[x] == false)
            {
                System.out.print("The missing integer is : "+(low + x)); 
            }
        } 
    } 
    public static void main(String[] args) 
    { 
        Scanner sc=new Scanner(System.in);
        int low=sc.nextInt();
        int high=sc.nextInt();
        int[] arr=new int[high-low];
        for(int index=0;index<high-low;index++)
        {
            arr[index]=sc.nextInt();
        }
        printMissing(arr, low, high); 
    } 
} 

input 1:
10 16
15 11 16 14 10 13

output 1:
The missing integer is : 12
Linear Search Implementation:

import java.util.Scanner;  
public class Main
{  
public static void main(String[] args)
{  
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int[] arr=new int[n];
    for(int index=0;index<n;index++)
    {
        arr[index]=sc.nextInt();
    }
    int item,flag=0;   
    item = sc.nextInt();  
    for(int i = 0; i<10; i++)  
    {  
        if(arr[i]==item)  
        {  
            flag = i+1;  
            break;  
        }  
        else   
            flag = 0;   
    }  
    if(flag != 0)  
    {  
        System.out.println("Item found at location " + flag);  
    }  
    else   
        System.out.println("Item not found");  
}  
}

input 1:
11
10 23 15 8 4 3 25 30 34 2 19
25

output 1:
Item found at location 7

input 2:
11
10 23 15 8 4 3 25 30 34 2 19
12

output 2:
Item not found
Binary Search Implementation:

import java.util.*;  
public class Main
{
    static int binarySearch(int[] a, int beg, int end, int item)  
   {  
    int mid;  
    if(end >= beg)   
    {     
        mid = (beg + end)/2;  
        if(a[mid] == item)  
        {  
            return mid+1;  
        }  
        else if(a[mid] < item)   
        {  
            return binarySearch(a,mid+1,end,item);  
        }  
        else   
        {  
            return binarySearch(a,beg,mid-1,item);  
        }  
      
    }  
    return -1;   
} 
public static void main(String[] args) 
{
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int[] arr=new int[n];
    for(int index=0;index<n;index++)
    {
        arr[index]=sc.nextInt();
    }
    int item, location = -1;   
    item = sc.nextInt();  
    location = binarySearch(arr,0,n-1,item);  
    if(location != -1)  
    System.out.println("The location of the item is "+location);  
    else   
        System.out.println("Item not found");  
    }  
}  

input 1:
10
16 19 20 23 45 56 78 90 96 100
23

output 1:
The location of the item is 4

input 2:
10
16 19 20 23 45 56 78 90 96 100
54

output 2:
Item not found
Jump search Implementation

import java.util.*;
public class Main
{ 
    static int jumpSearch(int[] arr, int x) 
    { 
        int n = arr.length; 
        int step = (int)Math.floor(Math.sqrt(n)); 
        int prev = 0; 
        while (arr[Math.min(step, n)-1] < x) 
        { 
            prev = step; 
            step += (int)Math.floor(Math.sqrt(n)); 
            if (prev >= n) 
                return -1; 
        } 
        while (arr[prev] < x) 
        { 
            prev++; 
            if (prev == Math.min(step, n)) 
                return -1; 
        } 
        if (arr[prev] == x) 
            return prev; 
        return -1; 
    } 
    public static void main(String [ ] args) 
    { 
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int index=0;index<n;index++)
        {
            arr[index]=sc.nextInt();
        }
        int item=sc.nextInt(); 
        int index1 = jumpSearch(arr, item); 
        System.out.println("Number " + item + " is at index " + index1); 
    } 
}

input 1:
16
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
55

output 1:
Number 55 is at index 10
Interpolation Search implementation:

import java.util.*;
public class Main
{
    static int interpolationSearch(int[] arr,int x) 
    { 
        int lo = 0, hi = (arr.length - 1); 
        while (lo <= hi && x >= arr[lo] && x <= arr[hi]) 
        {         
            if (lo == hi) 
            { 
                if (arr[lo] == x) return lo; 
                return -1; 
            }
            int pos = lo + (((hi-lo) / (arr[hi]-arr[lo]))*(x - arr[lo])); 
            if (arr[pos] == x) 
                return pos+1;
            if (arr[pos] < x) 
                lo = pos + 1; 
            else
                hi = pos - 1; 
        } 
        return -1; 
    } 
    public static void main(String[] args)  
    { 
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int index=0;index<n;index++)
        {
            arr[index]=sc.nextInt();
        }
         int item= sc.nextInt();
         int index1 = interpolationSearch(arr,item); 
         if (index1 != -1) 
               System.out.println("Element found at position " + index1); 
            else
               System.out.println("Element not found."); 
    } 
} 

input 1:
15
10 12 13 16 18 19 20 21 22 23 24 33 35 42 47
18

output 1:
Element found at position 5

input 2:
15
10 12 13 16 18 19 20 21 22 23 24 33 35 42 47
39

output 2:
Element not found.
Recursive Implementation of Ternary Search:

import java.util.*;
public class Main
{ 
    static int ternarySearch(int l, int r, int key, int ar[]) 
    { 
        if (r >= l) 
        { 
            int mid1 = l + (r - l) / 3; 
            int mid2 = r - (r - l) / 3; 
            if (ar[mid1] == key) 
            { 
                return mid1; 
            } 
            if (ar[mid2] == key)
            { 
                return mid2; 
            } 
            if (key < ar[mid1])
            { 
                return ternarySearch(l, mid1 - 1, key, ar); 
            } 
            else if (key > ar[mid2]) 
            {
                return ternarySearch(mid2 + 1, r, key, ar); 
            } 
            else 
            { 
                return ternarySearch(mid1 + 1, mid2 - 1, key, ar); 
            } 
        } 
        return -1; 
    } 
    public static void main(String args[]) 
    { 
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int index=0;index<n;index++)
        {
            arr[index]=sc.nextInt();
        }
        int key = sc.nextInt();
        int p = ternarySearch(0, n-1, key, arr); 
        System.out.println("Index of " + key + " is " + p); 
    } 
} 

input 1:
10
1 2 3 4 5 6 7 8 9 10
6

output 1:
Index of 6 is 5
Implementation of Exponential Search:

import java.util.*; 
public class Main
{ 
    static int exponentialSearch(int arr[],int n, int x) 
    { 
        if (arr[0] == x) 
            return 0; 
        int i = 1; 
        while (i < n && arr[i] <= x) 
            i = i*2; 
        return Arrays.binarySearch(arr, i/2,Math.min(i, n), x); 
    } 
    public static void main(String args[]) 
    { 
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int index=0;index<n;index++)
        {
            arr[index]=sc.nextInt();
        }
        int item = sc.nextInt(); 
        int result = exponentialSearch(arr, n, item); 
        System.out.println((result < 0) ? "Element is not present in array" : "Element is present at index " +  result); 
    } 
}

input 1:
5
2 3 5 10 50
10

output 1:
Element is present at index 4
Fibonacci Search Implementation:

import java.util.*; 
public class Main
{    
    public static int min(int x, int y)  
    { 
        return (x <= y)? x : y; 
    } 
    public static int fibMonaccianSearch(int arr[],int x, int n) 
    { 
        int fibMMm2 = 0;  
        int fibMMm1 = 1; 
        int fibM = fibMMm2 + fibMMm1;
        while (fibM < n) 
        { 
            fibMMm2 = fibMMm1; 
            fibMMm1 = fibM; 
            fibM = fibMMm2 + fibMMm1; 
        } 
        int offset = -1; 
        while (fibM > 1) 
        { 
            int i = min(offset+fibMMm2, n-1); 
            if (arr[i] < x) 
            { 
                fibM = fibMMm1; 
                fibMMm1 = fibMMm2; 
                fibMMm2 = fibM - fibMMm1; 
                offset = i; 
            }
            else if (arr[i] > x) 
            { 
                fibM = fibMMm2; 
                fibMMm1 = fibMMm1 - fibMMm2; 
                fibMMm2 = fibM - fibMMm1; 
            } 
            else return i; 
        } 
        if(fibMMm1 == 1 && arr[offset+1] == x) 
            return offset+1; 
        return -1; 
    } 
    public static void main(String[] args) 
    { 
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int index=0;index<n;index++)
        {
            arr[index]=sc.nextInt();
        }
        int x = sc.nextInt(); 
        System.out.print ("Found at index: "+fibMonaccianSearch(arr, x, n)); 
    } 
} 

input 1:
11
10 22 35 40 45 50 80 82 85 90 100
85

output 1:
Found at index: 8
Integers with atleast two repeating digits in a given range:

import java.util.*;
public class Main
{
    public static boolean valid(long n)
    {
        String str=String.valueOf(n);
        int l=str.length();
        int count[]=new int[10];
        for(int index=0;index<l;index++)
        {
            count[ str.charAt(index)-'0' ]++;
        }
        int c=0;
        for(int index=0;index<l;index++)
        {
            if(count[str.charAt(index)-'0' ]>=2 )
            {
                c++;
                count[str.charAt(index)-'0' ]=0;
            }
        }
        if(c>=2)
        return true;
        
        return false;
    }
    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        long a=sc.nextLong();
        long b=sc.nextLong();
        int flag=0;
        for(long index=a;index<=b;index++)
        {
            if(valid(index))
            {
                flag=1;
                System.out.print(index+" ");
            }
        }
        if(flag==0)
        System.out.print("-1");
    }
}

input 1:
1000 1025

output 1:
1001 1010

input 2:
18564 19678

output 2:
18581 18585 18616 18618 18661 18668 18681 18686 18717 18718 18771 18778 18781 18787 18800 18801 18810 18811 18812 18813 18814 18815 18816 18817 18818 18819 18821 18822 18831 18833 18841 18844 18851 18855 18861 18866 18871 18877 18881 18891 18899 18918 18919 18981 18989 18991 18998 19001 19009 19010 19019 19090 19091 19100 19109 19119 19122 19129 19133 19139 19144 19149 19155 19159 19166 19169 19177 19179 19188 19189 19190 19191 19192 19193 19194 19195 19196 19197 19198 19199 19212 19219 19221 19229 19291 19292 19313 19319 19331 19339 19391 19393 19414 19419 19441 19449 19491 19494 19515 19519 19551 19559 19591 19595 19616 19619 19661 19669 
Integers with atleast 3 distinct digits:

import java.util.*;
public class Main 
{
    static boolean findDistinctCount(String str)
    {
        Set<Character> st=new HashSet<>();
        int l=str.length();
        for(int index=0;index<l;index++)
        {
            st.add(str.charAt(index));
        }
        if(st.size()>=3)
        return true;
        else
        return false;
    }
    public static void main(String[] args)
    {
   Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int flag=0;
  for(int index=1;index<=n;index++)
  {
      String str=sc.next();
      if(findDistinctCount(str))
      {
          System.out.print(str+" ");
          flag=1;
      }
  }
  if(flag==0)
  System.out.print("-1");
 }
}

input 1:
5
56 65789 10 4567 325

output 1:
65789 4567 325

input 2:
8 
23 56739 77789 253 67 5 35648 2000456

output 2:
56739 77789 253 35648 2000456
Add adjacent till single value (4Lakh +CTC):

import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
   Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int[] arr=new int[n];
  for(int index=0;index<n;index++)
  {
      arr[index]=sc.nextInt();
  }
  int index1=0,arrSize=n;
  while(arrSize>1)
  {
      index1=0;
      for(int index=1;index<arrSize;index+=2)
      {
          arr[index1]=arr[index-1]+arr[index];
          index1++;
      }
      if(arrSize%2==1)
      {
          arr[index1]=arr[arrSize-1];
      }
      arrSize=(arrSize+1)/2;
      for(int index=0;index<arrSize;index++)
      {
          System.out.print(arr[index]+" ");
      }
      System.out.println();
  }
 }
}

input 1:
10
1 2 10 4 3 6 10 0 1 5
output 1:
3 14 9 10 6 
17 19 6 
36 6 
42 

explanation:
The given 10 integers are 1 2 10 4 3 6 10 0 1 and 5
(1+2),(10+4),(3+6),(10+0),(1+5) = 3, 14, 9, 10, 6
(3+14),(9+10),6 = 17, 19, 6
(17+19),6 = 36, 6
(36+6) = 42

input 2:
5
9 8 2 2 3
output 2:
17 4 3
21 3
24
Insert zero after K times 1 [ZOHO] :

import java.util.*;
public class Main
{
    public static void main(String[] args)
    {  
        Scanner sc=new Scanner(System.in);
        int count=0;
        int n=sc.nextInt();
        int k=sc.nextInt();
        for(int index=1;index<=n;index++)
        {
            int num=sc.nextInt();
            System.out.print(num+" ");
            if(num==1)
            {
                count++;
                if(count==k)
                {
                    count=0;
                    System.out.print("0 ");
                }
            }
            else
            {
                count=0;
            }
        }
 }
}

input 1:
14 2
1 0 1 1 0 1 1 0 1 0 0 1 1 0 
output 1:
1 0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 0 
Merge Sort - no dupliactes:

import java.util.*;
public class Main 
{
    public static void main(String[] args) 
    {
   Scanner sc=new Scanner(System.in);
  Set<Integer> hs=new HashSet<>();
  int m=sc.nextInt();
  int n=sc.nextInt();
  for(int index=0;index<m;index++)
  {
      hs.add(sc.nextInt());
  }
  for(int index=0;index<n;index++)
  {
      hs.add(sc.nextInt());
  }
  List<Integer> al=new ArrayList<>(hs);
  Collections.sort(al);
  for(int index=0;index<al.size();index++)
  {
      System.out.print(al.get(index)+" ");
  }
    }
}

input 1:
7 6
1 3 4 5 6 2 7 
4 1 5 8 10 9
output 1:
1 2 3 4 5 6 7 8 9 10
Count of Triplets - strictly increasing:

import java.util.*;
public class Main
{
    public static void main(String[] args) 
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int index=0;index<n;index++)
        {
            arr[index]=sc.nextInt();
        }
        int count=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                for(int k=j+1;k<n;k++)
                {
                    if((arr[i]<arr[j]&&arr[i]<arr[k])&&arr[j]<arr[k])
                    {
                        count++;
                    }
                }
            }
        }
        System.out.print(count);
  }
}

input 1:
5
3 4 1 8 7
output 1:
2

explanation:
the triplets that are strictly increasing are:
3->4->7
3->4->8

input 2:
10
1 5 17 29 3 9 10 4 8 12
output 2:
31
Array Integers -  from the last:

import java.util.*;
public class Main
{
    public static void main(String[] args) 
    {
   Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int[] arr=new int[n];
  for(int index=0;index<n;index++)
  {
      arr[index]=sc.nextInt();
  }
  Map<Integer,Integer> hm=new LinkedHashMap<>();
  int i=1;
  for(int index=n-1;index>=0;index--)
  {
      hm.put(i++,arr[index]);
  }
  for(int index=0;index<n;index++)
  {
      for(Map.Entry<Integer,Integer> m:hm.entrySet())
      {
          if(arr[index]==m.getKey())
          {
              System.out.print(m.getValue()+" ");
          }
      }
  }
 }
}

input 1:
6
6 1 4 2 3 4

output 1:
6 4 4 3 2 4

explanation:
the program must print the integer at the arr[index] position from the last 
eg:
when index=0;--> arr[index]->arr[0]=6. hence
6th integer from last is 6 ;
1st integer from last is 4;
4th integer from last is 4 ;
2nd integer from last is 3;
3rd integer from last is 2 ;
4th integer from last is 4;
Array Elements adjacent odd/even compression:

import java.util.*;
public class Main 
{
    public static void main(String[] args) 
    {  
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        List<Integer> al=new ArrayList<>();
        for(int index=0;index<n;index++)
        {
            al.add(sc.nextInt());
        }
        boolean flag=true;
        while(true)
        {
            flag=true;
            for(int index=0;index<al.size();index++)
            {
                if((index!=al.size()-1)&&((al.get(index)%2==0&&al.get(index+1)%2==0)||(al.get(index)%2==1&&al.get(index+1)%2==1)))
                {
                    al.remove(index+1);
                    flag=false;
                }
            }
            if(flag==true)
            break;
        }
        for(Integer num:al)
        {
            System.out.print(num+" ");
        }
 }
}

input 1:
8
44 66 13 49 41 4 80 36

output 1:
44 13 4
Sum of digits - concatenated :

import java.util.*;
public class Main 
{
    public static void main(String[] args) 
    {
    Scanner sc=new Scanner(System.in);
    char arr[]=sc.next().toCharArray();
    int l=arr.length;
    long ans=0;
    
    for(int i=0;i<l;i++)
    {
       String k="";
       int num=arr[i]-'0';
       while(num != -1)
       {
           k+=num+""; num--; 
       }
       long val=Long.parseLong(k);
       ans+=val;
    }
    System.out.print(ans);
  }
}

input 1:
4093

output 1:
9876589630 

explanation:
(43210) + 0 + (9876543210) + (3210) = 9876589630 
the number is concatenated till 0 and then added seperately to print the output
Count Distinct elements in an array:

import java.util.*;
public class Main 
{
    public static void main(String[] args) 
    {
   Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int m=sc.nextInt();
  List<Integer> al=new ArrayList<>();
  for(int index1=0;index1<n;index1++)
  {
      al.add(sc.nextInt());
  }
  for(int index2=0;index2<m;index2++)
  {
      al.add(sc.nextInt());
  }
  Map<Integer,Integer> hm=new LinkedHashMap<>();
  int count=0;
  for(int index=0;index<al.size();index++)
  {
      if(hm.containsKey(al.get(index)))
      {
          count=hm.get(al.get(index));
          hm.put(al.get(index),++count);
      }
      else
      {
          hm.put(al.get(index),1);
      }
  }
  int ctr=0;
  for(Map.Entry<Integer,Integer> p:hm.entrySet())
  {
      if(p.getValue()==1)
      {
          ctr++;
      }
  }
  System.out.print(ctr);
    }
}

input 1:
5 4
1 2 17 19 5
2 4 8 5
output 1:
5
Maximum Integer at Kth position:

import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
   Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int k=sc.nextInt();
  List<Integer> al1=new ArrayList<>();
  List<Integer> al2=new ArrayList<>();
  for(int index=0;index<n;index++)
  {
      al1.add(sc.nextInt());
  }
  Collections.sort(al1,Collections.reverseOrder());
  int max=Collections.max(al1);
  al1.remove(0);
  int j=0;
  for(int index=0;index<n;index++)
  {
      if(index==k-1)
      {
          al2.add(max);
      }
      else
          al2.add(al1.get(j++));
  }
  for(Integer num:al2)
      System.out.print(num+" ");
 }
}

input 1:
5 3
10 21 75 50 48
output 1:
50 48 75 21 10 

explanation:
the maximum num is 75. at kth position, max is placed and for remaining index, the rest elements are stired in descending order.

input 2:
8 2
10 45 17 28 19 89 9 34
output 2:
45 89 34 28 19 17 10 9
Maximum at Kth position:

import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
   Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int k=sc.nextInt();
  List<Integer> al1=new ArrayList<>();
  List<Integer> al2=new ArrayList<>();
  for(int index=0;index<n;index++)
  {
      al1.add(sc.nextInt());
  }
  Collections.sort(al1,Collections.reverseOrder());
  int max=Collections.max(al1);
  al1.remove(0);
  int j=0;
  for(int index=0;index<n;index++)
  {
      if(index==k-1)
      {
          al2.add(max);
      }
      else
          al2.add(al1.get(j++));
  }
  for(Integer num:al2)
      System.out.print(num+" ");
 }
}

input 1:
5 3
10 21 75 50 48
output 1:
50 48 75 21 10 

explanation:
the maximum num is 75. at kth position, max is placed and for remaining index, the rest elements are stired in descending order.

input 2:
8 2
10 45 17 28 19 89 9 34
output 2:
45 89 34 28 19 17 10 9
Count of Triplets - Strictly increasing:

import java.util.*;
public class Main
{
    public static void main(String[] args) 
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int index=0;index<n;index++)
        {
            arr[index]=sc.nextInt();
        }
        int count=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                for(int k=j+1;k<n;k++)
                {
                    if((arr[i]<arr[j]&&arr[i]<arr[k])&&arr[j]<arr[k])
                    {
                        count++;
                    }
                }
            }
        }
        System.out.print(count);
  }
}

input 1:
5
3 4 1 8 7
output 1:
2

explanation:
the triplets that are strictly increasing are:
3->4->7
3->4->8

input 2:
10
1 5 17 29 3 9 10 4 8 12
output 2:
31
Count of integers small to its left:

import java.util.*;
public class Main 
{

    public static void main(String[] args) 
    {
   Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int[] arr=new int[n];
  for(int index=0;index<n;index++)
  {
      arr[index]=sc.nextInt();
  }
  System.out.print("0 ");
  for(int index=1;index<n;index++)
  {
      int count=0;
      for(int i=index-1;i>=0;i--)
      {
          if(arr[i]<arr[index])
          {
              count++;
          }
          else
          {
              break;
          }
      }
      System.out.print(count+" ");
  }
 }
}

input 1:
6                                                                                                                             
100 200 105 110 120 100  

output 1:
0 1 0 1 2 0
Integers  - equal to index value:

import java.util.*;
public class Main
{
    public static void main(String[] args) 
    {
   Scanner sc=new Scanner(System.in);
  int flag=0;
  int n=sc.nextInt();
  int[] arr=new int[n];
  for(int index=0;index<n;index++)
  {
      arr[index]=sc.nextInt();
      if(arr[index]==index)
      {
          System.out.print(index+" ");
          flag=1;
      }
  }
  if(flag==0)
  System.out.print("-1");
 }
}

input 1:
6
4 3 2 3 6 5
output 1:
2 3 5

input 2:
4
7 2 5 8
output 2:
-1
Arrays - sorted in descending order or not:

import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
   Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  List<Integer> arr1=new ArrayList<>();
  List<Integer> arr2=new ArrayList<>();
  for(int index=0;index<n;index++)
  {
      arr1.add(sc.nextInt());
      arr2.add(arr1.get(index));
  }
  Collections.sort(arr2,Collections.reverseOrder());
  if(arr1.equals(arr2))
  System.out.print("yes");
  else
  System.out.print("no");
 }
}

input 1:
5                                                                                                                             
100 50 47 36 21  
output 1:
yes

input 2:
7                                                                                                                             
35 92 36 29 45 29 45 
output 2:
no
Integer and position - odd/even:

import java.util.*;
public class Main
{
    public static void main(String[] args) 
    {
        Scanner sc=new Scanner(System.in);
        int flag=0;
        int n=sc.nextInt();
        int[] arr=new int[n+1];
        for(int index=1;index<=n;index++)
        {
            arr[index]=sc.nextInt();
            if(arr[index]%2==0&&index%2==1||(arr[index]%2==1||arr[index]%2==-1)&&index%2==0)
            {
                    System.out.print(arr[index]+" ");
                    flag=1;
            }
        }
        if(flag==0)
        System.out.print("-1");
  }
}

input 1:
5                                                                                                                             
80 45 -67 23 50 
output 1:
80 45 23 50

explanation:
if the integer is odd and the position is even or integer is even and the position is odd, then it is printed. 
else not printed. if no such integer, then -1 is printed as output.

input 2:
4                                                                                                                             
45 60 5 2 
outptu 2:
-1
Two integer sum equal to K - yes/no:

import java.util.*;
public class Main 
{
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long k=sc.nextLong();
        long[] arr=new long[n];
        for(int index=0;index<n;index++)
        {
            arr[index]=sc.nextLong();
        }
        int flag=0;
        OUTER:for(int index1=0;index1<n;index1++)
        {
            for(int index2=index1+1;index2<n;index2++)
            {
                if(arr[index1]+arr[index2]==k)
                {
                    System.out.print("yes");
                    flag=1;
                    break OUTER;
                }
            }
        }
        if(flag==0)
        System.out.print("no");
  }
}

input 1:
5 10
2 8 6 7 4
output 1:
yes

input 2:
8 19
6 8 7 4 2 0 4 1
output 2:
no

Position of minimum and maximum integer:


import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();

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

List<Integer> al=new ArrayList<>();

for(int index=1;index<=n;index++)

{

arr[index]=sc.nextInt();

al.add(arr[index]);

}

Collections.sort(al);

int min=al.get(0),max=al.get(al.size()-1);

int minPos=0,maxPos=0;

for(int index=1;index<=n;index++)

{

if(arr[index]==min)

minPos=index;

else if(arr[index]==max)

maxPos=index;

}

System.out.print(minPos+" "+maxPos);

}

}


input 1:

10

78 67 5 43 89 02 46 13 20 9


output 1:

6 5


explanation:

the position of minimum and maximum integer is printed as output

Find kth largest element in the array:

import java.util.*;
public class Main
{
  public static void main (String[]args)
  {
    Scanner sc = new Scanner (System.in);
      List < Integer > al = new ArrayList <> ();
    int n = sc.nextInt ();
    int k = sc.nextInt ();
    for (int index = 0; index < n; index++)
        al.add (sc.nextInt ());
      Collections.sort (al, Collections.reverseOrder ());
      Set < Integer > st = new LinkedHashSet <> (al);
      List < Integer > arr = new ArrayList <> (st);
      System.out.print (arr.get (k - 1));
  }
}

input 1:
9 3                                                                                                                            3
28 89 67 90 26 48 29 95 56                                                                                                      

output 1:
89
Inplace sort of odd and even integers:

import java.util.*;

public class Main
{
    static void replace(int[] arr,int n,List<Integer> al,List<Integer> position)
    {
        for(int index1=0;index1<al.size();index1++)
        {
            for(int index2=0;index2<n;index2++)
            {
                if(index2==position.get(index1))
                arr[index2]=al.get(index1);
            }
        }
    }
    public static void main(String[] args) 
    {
   Scanner sc=new Scanner(System.in);
  List<Integer> al=new ArrayList<>();
  List<Integer> position=new ArrayList<>();
  int n=sc.nextInt();
  int[] arr=new int[n];
  for(int index=0;index<n;index++)
  {
      arr[index]=sc.nextInt();
      if(arr[index]%2==1)
      {
          al.add(arr[index]);
          position.add(index);
      }
  }
  Collections.sort(al);
  replace(arr,n,al,position);
  al.clear();
  position.clear();
  for(int index=0;index<n;index++)
  {
      if(arr[index]%2==0)
      {
          al.add(arr[index]);
          position.add(index);
      }
  }
  Collections.sort(al);
  replace(arr,n,al,position);
  for(Integer index : arr)
  System.out.print(index+" ");
 }
}

input 1:
11
46 20 55 43 83 73 66 90 25 79 50

output 1:
20 46 25 43 55 73 50 66 79 83 90 

input 2:
6
19 56 81 15 16 82

output 2:
15 16 19 81 56 82 
Inplace sort of odd and even integers (using XOR):

import java.util.*;
public class Main
{
    public static void main(String[] args) 
    {
  Scanner sc=new Scanner(System.in);
 int N=sc.nextInt();
 int []arr=new int[N];
 for(int index=0;index<N;index++)
 {
     arr[index]=sc.nextInt();
 }
    for(int index1=0;index1<N;index1++)
    {
        for(int index2=index1;index2<N;index2++)
        {
            if(arr[index1]%2==0&&arr[index2]%2==0&&arr[index1]>arr[index2])
            {
                arr[index1]^=arr[index2];
                arr[index2]^=arr[index1];
                arr[index1]^=arr[index2];
            }
            else if(arr[index1]%2==1&&arr[index2]%2==1&&arr[index1]>arr[index2])
            {
                arr[index1]^=arr[index2];
                arr[index2]^=arr[index1];
                arr[index1]^=arr[index2];
            }
        }
    }
    for(int index : arr)
        System.out.print(index+" ");
 }
}

input 1:
11
46 20 55 43 83 73 66 90 25 79 50

output 1:
20 46 25 43 55 73 50 66 79 83 90 

input 2:
6
19 56 81 15 16 82

output 2:
15 16 19 81 56 82 
Inplace reverse of first K and last K integers:

import java.util.*;
public class Main 
{
    static void Reverse(int[] arr,int start,int end)
    {
        Stack<Integer> st=new Stack<>();
        for(int index=start;index<end;index++)
        {
            st.push(arr[index]);
        }
        for(int index=start;index<end;index++)
        {
            arr[index]=st.pop();
        }
        st.clear();
    }
    public static void main(String[] args)
    {
   Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int[] arr=new int[n];
  for(int index=0;index<n;index++)
  {
      arr[index]=sc.nextInt();
  }
  int k=sc.nextInt();
  Reverse(arr,0,k);
  Reverse(arr,n-k,n);
  for(Integer index : arr)
  System.out.print(index+" ");
 }
}

input 1:
6
1 2 3 4 5 6
3

output 1:
3 2 1 6 5 4
Remove last occurrence of k:

import java.util.*;
public class Main 
{
    public static void main(String[] args) 
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        List<Integer> al=new ArrayList<>();
        for(int index=0;index<n;index++)
        {
            al.add(sc.nextInt());
        }
        int k=sc.nextInt();
        for(int index=al.size()-1;index>=0;index--)
        {
            if(al.get(index)==k)
            {
               al.remove(index);
               break;
            }
        }
        for(int index=0;index<al.size();index++)
        {
            System.out.print(al.get(index)+" ");
        }
  }
}

input 1:
5                                                                                                                               
67 86 34 29 86                                                                                                                  
67 

output 1:
86 34 29 86
Sort based on count of zeros:

import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
   Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int arr[]=new int[n];
  int binary[]=new int[n];
  for(int index=0;index<n;index++)
  {
      arr[index]=sc.nextInt();
      int x=arr[index],c=0;
      while(x>0)
      {
          if(x%2==0)
          c++;
          x/=2;
      }
      binary[index]=(c*100)+index;
  }
       Arrays.sort(binary);
       for(int index=0;index<n;index++)
       {
           System.out.print(arr[binary[index]%100]+" ");
       }
 }
}

input 1:
5
47 688 14 64 54

output 1:
47 14 54 688 64 

input 2:
8 
10 65 7992 46 2973 62 985 78

output 2:
62 10 46 985 78 2973 65 7992
Reverse alternate k integers:

import java.util.*;
public class Main 
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] array = new int[N];
        for(int index=0;index<N;index++)
        {
            array[index] = sc.nextInt();
        }
        int K = sc.nextInt();
        int flag = 0;
        for(int index=0;index<N;index+=K)
        {
            if(flag == 0)
            {
                int start = index;
                int end;
                if(N > (index+K-1))
                {
                    end = index+K-1;
                }
                else
                {
                    end = N-1;
                }
                while(start<end){
                    int temp = array[start];
                    array[start++] = array[end];
                    array[end--] = temp;
                }
                flag = 1;
            }
            else
            {
                flag = 0;
            }
        }
        for(int index=0;index<N;index++)
        {
            System.out.print(array[index]+" ");
        }
  }
}

input 1:
9
9 2 4 5 7 5 2 3 9                                                                                                             
2     
output 1:
2 9 4 5 5 7 2 3 9

input 2:
5
1 2 3 4 5
3
output 2:
3 2 1 4 5
Sum of Subarray equals K:

import java.util.*;
public class Main 
{
    public static void main(String[] args) 
    {
   Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int[] arr=new int[n];
  for(int index=0;index<n;index++)
  {
      arr[index]=sc.nextInt();
  }
  int k=sc.nextInt();
  int currSum=arr[0],flag=0;
  for(int index1=0,index2=0;index1<n&&index2<n;)
  {
      if(currSum==k)
      {
          System.out.print("Yes");
          flag=1;
          break;
      }
     else if(currSum<k)
     {
         index1++;
         if(index1<n)
         currSum+=arr[index1];
     }
     else
     {
         currSum-=arr[index2];
         index2++;
     }
  }
  if(flag==0)
  System.out.print("No");
 }
}

input 1:
6
4 7 1 5 4 6
14
output 1:
No

input 2:
5
5 10 50 20 25
45
output 2:
Yes
Majority element in an array:

import java.util.*;
public class Main
{
    public static void main(String[] args) 
    {
   Scanner sc=new Scanner(System.in);
  Map<Integer,Integer> hm=new HashMap<>();
  int count=0,n=sc.nextInt();
  for(int index=0;index<n;index++)
  {
      int num=sc.nextInt();
      if(hm.containsKey(num))
      {
          count=hm.get(num);
          hm.put(num,++count);
      }
      else
      hm.put(num,1);
  }
  int flag=0;
  for(Map.Entry<Integer,Integer> m:hm.entrySet())
  {
      if(m.getValue()>n/2)
      {
          System.out.print(m.getKey());
          flag=1;
          break;
      }
  }
  if(flag==0)
  System.out.print("No Majority Element");
 }
}

input 1:
8                                                                                                                             
2 5 7 2 2 2 2 2                                                                                                               
2

output 1:
2

explanation: 
if it is a majority element, then it should repeat more than n/2 times.

input 2:
10
2 3 7 3 5 3 6 3 8 2

output 2:
No majority elements
Sort based on frequency of occurences:

import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
   Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
  int[] arr = new int[n];
  Map<Integer, Integer> hm = new HashMap<>();
  for(int i=0;i<n;i++)
  {
      arr[i] = sc.nextInt();
      hm.put(arr[i], hm.getOrDefault(arr[i], 0)+1);
  }
  for(int i=0;i<n;i++)
  {
      for(int j=i+1;j<n;j++)
      {
          if(hm.get(arr[i]) == hm.get(arr[j]))
          {
              if(arr[i]<arr[j])
              {
                  arr[i]=arr[i]^arr[j];
                  arr[j] = arr[i]^arr[j];
                  arr[i] = arr[i]^arr[j];
              }
              continue;
          }
          if(hm.get(arr[i]) < hm.get(arr[j]))
          {
              arr[i]=arr[i]^arr[j];
              arr[j] = arr[i]^arr[j];
              arr[i] = arr[i]^arr[j];
          }
      }
  }
  for(int index=n-1;index>=0;index--)
  {
      System.out.print(arr[index] + " ");
  }
 }
}

input 1:
5                                                                                                                             
10 30 30 20 30 
output 1:
10 20 30 30 30
Replace with next immediate small value to the left:

import java.util.*;
public class Main 
{
    public static void main(String[] args)
    {
   Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  long[] arr=new long[n];
  for(int index=0;index<n;index++)
  {
      arr[index]=sc.nextLong();
  }
  long min=arr[0];
  for(int index=1;index<n;index++)
  {
      if(arr[index]<min)
      min=arr[index];
      else
      arr[index]=min;
  }
  for(Long num:arr)
  System.out.print(num+" ");
 }
}

input 1:
6                                                                                                                             
60 50 40 40 60 80  

output 1:
60 50 40 40 40 40