#include <bits/stdc++.h>
using namespace std;

int largest(int arr[],int n){
  int maxi = INT_MIN;
  for(int i = 0;i<n;i++){
    maxi = max(maxi,arr[i]);
  }
  return maxi;
}

int Second_Largest(int arr[],int n){
  int Largest = arr[0];
  int Second_Largest = -1;
  for(int i = 1;i<n;i++){
    if(arr[i] > Largest){
      Second_Largest = Largest;
      Largest = arr[i];
    }
    if(arr[i] < Largest && arr[i] > Second_Largest){
      Second_Largest = arr[i];
    }
  }
  return Second_Largest;
}

bool check_sort(int arr[],int n){
  for(int i = 0;i<n-1;i++){
    if(arr[i] > arr[i+1]){
      return false;
    }
  }
  return true;
}

//1 1 2 2 2 3 3 4 5

int  remove_dups(int arr[],int n){
  //Brute force : one approach is to use set;
  // -------------or------------------
  //optimal: 2 pointer approach
  int i = 0,j=0;
  while(j<n){
    if(arr[i] == arr[j]){
      j++;
    }
    else{
      swap(arr[i+1],arr[j]);
      i++;
      j++;
    }
  }
  return i+1;
}

void leftRotateByOne(int a[],int n){
  int temp = a[0];
  for(int i = 0;i<n-1;i++){
    a[i] = a[i+1];
  }
  a[n-1] = temp;
}

void leftRotateByD(int a[],int n,int d){
  d = d%n;
  //store d then intialize arr with n-d Elements and then intialize the remaining d Elements
  reverse(a,a+d);
  reverse(a+d,a+n);
  reverse(a,a+n);
}

void move_Zeros_To_End(int arr[],int n){
  int i = 0,j=1;
  while(j<n){
    if(arr[i] != 0 ){
      i++;
      j++;
    }
    else if(arr[i] == 0 && arr[j] !=0){
      swap(arr[i],arr[j]);
      i++;
      j++;
    }
    else{
      j++;
    }
  }
}

vector<int> Union_Arrays(int n1[],int n2[],int n1_Size,int n2_size){
  //Using Set DS 
  //-------------or------------------
  // 2 pointer
  int p1 = 0,p2 = 0,k = 0;
  vector<int> Union;
  while(p1 < n1_Size && p2 < n2_size){
    if(n1[p1]<=n2[p2]){
      if (Union.empty() || Union.back() != n1[p1]) {
                Union.push_back(n1[p1]);
                
      }
      p1++;
    }
    else{
      if (Union.empty() || Union.back() != n2[p2]) {
                Union.push_back(n2[p2]);
                
      }
      p2++;
    }
  }
  while(p1 < n1_Size){
    if (Union.empty() || Union.back() != n1[p1]) {
                Union.push_back(n1[p1]);
    }
    p1++;
  }
  while(p2 < n2_size){
    if (Union.empty() || Union.back() != n2[p2]) {
                Union.push_back(n2[p2]);
    }
    p2++;
  }
  return Union;
}

int missing_element(int miss[],int n){
  //brute for  ---> O(n^@)
  //set DS
  //sum or Xor (XOR IS slightly better than sum in terms of memory)
  int XOR1 = 0,XOR2 = 0;
  for(int i = 0;i<n-1;i++){
    XOR1 ^= miss[i];
    XOR2 ^= i+1;
  }
  return XOR1^XOR2^n;
}

int maxi_ones(int nums[],int n){
  int cnt =0,maxi = 0;
  for(int i = 0;i<n;i++){
    if(nums[i] == 1){
        cnt++;
        maxi = max(maxi,cnt);
    }
    else{
        cnt = 0;
    }
  }
  return maxi;
}
int main() 
{
    cout << "Largest Element in an Array" << endl;
    int n;
    cin >> n;
    int arr[n];
    for(int i = 0;i<n;i++) cin>>arr[i];
    cout << "largest = " << largest(arr,n) << endl <<endl;
    
    //Second Largest Element in an Array without sorting
    cout <<"Second Largest Element in an Array without sorting"<<endl;
    cout << "Second_Largest: "<<Second_Largest(arr,n)<<endl<<endl;
    
    //Check if the array is sorted
    cout << "Check if the array is sorted" <<endl;
    cout << "if the array is sorted : " << check_sort(arr,n) << endl << endl;
    
    //Remove duplicates from Sorted array
    cout<< "Remove duplicates from Sorted array" << endl;
    int idx = remove_dups(arr,n);
    for(int i = 0;i<idx;i++) cout<<arr[i]<<" ";
    cout<<endl<<endl;
    
    //Left Rotate an array by one place
    cout << "Left Rotate an array by one place"<<endl;
    int a[] = {1,2,3,4,5};
    leftRotateByOne(a,5);
    for(int i = 0;i<5;i++) cout<<a[i]<<" ";
    cout<<endl<<endl;
    
    //Left rotate an array by D places
    cout << "Left rotate an array by D places"<<endl;
    int lfa [] = {1,2,3,4,5,6,7};
    int lfa_size = sizeof(lfa)/sizeof(lfa[0]);
    int d = 3;
    leftRotateByD(lfa,lfa_size,d);
    for(int i = 0;i<lfa_size;i++) cout<<lfa[i]<<" ";
    cout<<endl<<endl;
    //for right rotate 
    // rev(a,a+d+1) , rev(a+d+1,a+n) ,rev(a,a+n)
    
    //Move Zeros to end
    int mze[] = {2,0,1,1,0,1,1,1,0};
    cout << "Move Zeros to end"<<endl;
    int mze_size = sizeof(mze)/sizeof(mze[0]);
    move_Zeros_To_End(mze,mze_size);
     for(int i = 0;i<mze_size;i++) cout<<mze[i]<<" ";
    cout<<endl<<endl;
    
    //Union of Two Sorted Arrays
    // n = 10,m = 7.
    // arr1[] = {1,2,3,4,5,6,7,8,9,10}
    // arr2[] = {2,3,4,4,5,11,12}
    // Output:
    //         {1,2,3,4,5,6,7,8,9,10,11,12}
    // Explanation:
  
    cout<<"Union of Two Sorted Arrays"<<endl;
    int n1[] = {1,2,3,4,5,6,7,8,9,10};
    int n2[] = {2,3,4,4,5,11,12};
    int n1_size = sizeof(n1)/sizeof(n1[0]);
    int n2_size = sizeof(n2)/sizeof(n2[0]);
    vector<int> ans = Union_Arrays(n1,n2,n1_size,n2_size);
    for(auto it:ans){
      cout<<it << " ";
    }
    cout<<endl<<endl;
    
    //Find the missing number in an array
    cout<<"Find the missing number in an array"<<endl;
    // Input Format:
    // N = 5, array[] = {1,2,4,5}
    // Result: 3
    // Explanation: 
    // In the given array, number 3 is missing. So, 3 is the answer.
    int miss[] ={1,2,4,5};
    int miss_size = sizeof(miss)/sizeof(miss[0]);
    cout << "missing Element in array is: " << missing_element(miss,miss_size);
    
    //Maximum consecutive  1's 
    cout << "Maximum consecutive  1's "<<endl;
    // Example 1:
    // Input: prices = {1, 1, 0, 1, 1, 1}
    // Output: 3
    int bin[] = {1, 1, 0, 1, 1, 1};
    int bin_size = sizeof(bin)/sizeof(bin[0]);
    cout << "max 1's: "<< maxi_ones(bin,bin_size)<<endl<<endl;
  
    
    return 0;
}