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:

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:

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:

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:

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:

1 5 10 15 20 25

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:

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:

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:

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:

10 20 30 40

40 30 20 10

output 1:

input 2:

10 20 30 40 50

50 30 20 40 10

output 2:

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:

10 23 15 8 4 3 25 30 34 2 19

output 1:

Item found at location 7

input 2:

10 23 15 8 4 3 25 30 34 2 19

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:

16 19 20 23 45 56 78 90 96 100

output 1:

The location of the item is 4

input 2:

16 19 20 23 45 56 78 90 96 100

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:

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

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:

10 12 13 16 18 19 20 21 22 23 24 33 35 42 47

output 1:

Element found at position 5

input 2:

10 12 13 16 18 19 20 21 22 23 24 33 35 42 47

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:

1 2 3 4 5 6 7 8 9 10

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:

2 3 5 10 50

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:

10 22 35 40 45 50 80 82 85 90 100

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:

56 65789 10 4567 325

output 1:

65789 4567 325

input 2:

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:

1 2 10 4 3 6 10 0 1 5

output 1:

3 14 9 10 6

17 19 6

36 6

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:

9 8 2 2 3

output 2:

17 4 3

21 3

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:

3 4 1 8 7

output 1:

explanation:

the triplets that are strictly increasing are:

3->4->7

3->4->8

input 2:

1 5 17 29 3 9 10 4 8 12

output 2:

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 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:

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:

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:

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:

3 4 1 8 7

output 1:

explanation:

the triplets that are strictly increasing are:

3->4->7

3->4->8

input 2:

1 5 17 29 3 9 10 4 8 12

output 2:

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:

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:

4 3 2 3 6 5

output 1:

2 3 5

input 2:

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:

100 50 47 36 21

output 1:

yes

input 2:

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:

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:

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:

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:

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:

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:

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:

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:

1 2 3 4 5 6

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:

67 86 34 29 86

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:

47 688 14 64 54

output 1:

47 14 54 688 64

input 2:

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 2 4 5 7 5 2 3 9

output 1:

2 9 4 5 5 7 2 3 9

input 2:

1 2 3 4 5

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:

4 7 1 5 4 6

output 1:

No

input 2:

5 10 50 20 25

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:

2 5 7 2 2 2 2 2

output 1:

explanation:

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

input 2:

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:

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:

60 50 40 40 60 80

output 1:

60 50 40 40 40 40