// Author : Khadiza Sultana
// Date : 1/4/2025
#include <iostream>
#include <vector>
using namespace std;

int search(vector<int>& nums, int target) {
    int st = 0, end = nums.size() - 1;
    while (st <= end) {
        int mid = st + (end - st) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[st] <= nums[mid]) { // Left half is sorted
            if (nums[st] <= target && target <= nums[mid]) {
                end = mid - 1;
            } else {
                st = mid + 1;
            }
        } else { // Right half is sorted
            if (nums[mid] <= target && target <= nums[end]) {
                st = mid + 1;
            } else {
                end = mid - 1;
            }
        }
    }
    return -1;
}

int main() {
    vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
    int target = 0;

    int result = search(nums, target);

    if (result != -1) {
        cout << "Target " << target << " found at index: " << result << endl;
    } else {
        cout << "Target " << target << " not found in the array." << endl;
    }

    return 0;
}

// Author : Khadiza Sultana
// Date : 1/4/2025
#include<iostream>
#include<vector>
using namespace std;

int binarySearch(vector<int>&arr, int tar) { // practical implementation
    int n = arr.size();
    int st = 0, end = n-1;
    while(st <= end) {
        int mid = st + (end-st)/2; // not using (st+end)/2 to avoid integer overflow
        if (tar > arr[mid]) {
            st = mid+1;
        }
        else if (tar < arr[mid]) {
            end = mid-1;
        }
        else {
            return mid;
        }
    }
    return -1;
}

int binarySearch2(vector<int>&arr, int tar, int st, int end) { // recursive implementation
    if (st > end) { // base case
        return -1;
    }
    int mid = st + (end-st)/2;
    if (tar > arr[mid]) {
        binarySearch2(arr, tar, mid+1, end);
    }
    else if (tar < arr[mid]) {
        binarySearch2(arr, tar, st, mid-1);
    }
    else {
        return mid;
    }
}

int main() {
    vector<int>arr1 = {3, 5, 7, 12, 15, 18}; // even no of elements
    int tar1 = 3;
    vector<int>arr2 = {4, 6, 10, 11, 12, 18, 19}; // odd no of elements
    int tar2 = 19;

    cout << "Index at which tar1 is found(even no of elements) : " << binarySearch(arr1, tar1) << endl;
    cout << "Index at which tar2 is found(odd no of elements) : " << binarySearch(arr2, tar2) << endl;
    
    cout << "Using Recusive function index at which tar1 is found : " << binarySearch2(arr1, tar1, 0, 5) << endl;
    cout << "Using Recusive function index at which tar1 is found : " << binarySearch2(arr2, tar2, 0, 6) << endl;

    return 0;
}

bool binarySearch(int arr[], int s, int e, int key) {
  if (s > e)
    return false;
  int mid = s + (e - s) / 2;
  if (arr[mid] == key)
    return true;
  if (arr[mid] < key)
    return binarySearch(arr, mid + 1, e, key);
  else
    return binarySearch(arr, s, mid - 1, key);
}

#include <iostream>
using namespace std;

void printArray (int arr[],int n) {
  for (int i= 0; i< n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

void sortArray (int arr[], int n) {
  for (int i = 0; i < (n-1); i ++) {
    for (int j = (i+1); j < n; j++) {
      if (arr[i] > arr[j]) {
        swap (arr[i], arr[j]);
      }
    }
  }
}

int main () {
  int n;
  cout << "Enter the size of the array: " << endl;
  cin >> n;
  int arr[n];
  cout << "Enter the elements of the array: " << endl;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  cout << "The array before sorting: " << endl;
  printArray (arr, n);
  sortArray (arr, n);
  cout << "the array after sorting :" << endl;
  printArray(arr,n);
  return 0;
}

#include <iostream>
using namespace std;

bool allocationIsPossible(int arr[], int n, int m, int mid) {
    int sum = 0;
    int studentCount = 1;
    for (int i = 0; i < n; i++) {
        if (sum + arr[i] <= mid) {
            sum += arr[i];
        } else {
            studentCount++;
            if (studentCount > m || arr[i] > mid) {
                return false;
            }
            sum = arr[i];
        }
    }
    return true;
}

int bookAllocate(int arr[], int n, int m) {
    int start = 0;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    int end = sum;
    int mid = start + (end - start) / 2;
    int ans = -1;
    while (start <= end) {
        if (allocationIsPossible(arr, n, m, mid)) {
            ans = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }
        mid = start + (end - start) / 2;
    }
    return ans;
}

int main() {
    int arr[4] = {10, 20, 30, 40};
    int ans = bookAllocate(arr, 4, 2);
    cout << "Minimum pages: " << ans << endl;
    return 0;
}
  

// output is 60

#include <iostream>
using namespace std;

bool allocationIsPossible(int arr[], int n, int m, int mid) {
    int sum = 0;
    int studentCount = 1;
    for (int i = 0; i < n; i++) {
        if (sum + arr[i] <= mid) {
            sum += arr[i];
        } else {
            studentCount++;
            if (studentCount > m || arr[i] > mid) {
                return false;
            }
            sum = arr[i];
        }
    }
    return true;
}

int bookAllocate(int arr[], int n, int m) {
    int start = 0;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    int end = sum;
    int mid = start + (end - start) / 2;
    int ans = -1;
    while (start <= end) {
        if (allocationIsPossible(arr, n, m, mid)) {
            ans = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }
        mid = start + (end - start) / 2;
    }
    return ans;
}

int main() {
    int arr[4] = {10, 20, 30, 40};
    int ans = bookAllocate(arr, 4, 2);
    cout << "Minimum pages: " << ans << endl;
    return 0;
}
  

// output is 60

class Solution {
public:
    vector<int> duplicates(vector<int>& nums){
        unordered_set<int> uSet;
        int n = nums.size();
        vector<int> dup(n, 0);
        for(int i = 0 ; i < n ;i++){
            if(uSet.find(nums[i]) != uSet.end()){
                dup[i] = 1;
            }
            if(i != 0)
                dup[i] += dup[i-1];
            uSet.insert(nums[i]);
        }
        return dup;
    }
    int minOperations(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int req = nums.size() - 1 , ans = nums.size() - 1, n =nums.size();
        vector<int> d = duplicates(nums);
        for(int ptr = 0; ptr < n-1 ;ptr++ ){
            int idx = lower_bound(nums.begin(), nums.end(), req + nums[ptr]) - nums.begin();
            if(idx < n ){
                int val = nums[ptr] + req;
                if(nums[idx] != val)
                    ans = min(ans, n - idx + ptr + d[idx] - d[ptr]);
                else
                    ans = min(ans, n - idx + ptr - 1 + d[idx] - d[ptr]);
            } 
            else
                ans = min(ans, d[n-1] - d[ptr]+ptr);
        }
        return ans;

    }
};

#include <stdio.h>  
int binarySearch(int a[], int beg, int end, int val)    
{    
    int mid;    
    if(end >= beg)     
    {        mid = (beg + end)/2;    
/* if the item to be searched is present at middle */  
        if(a[mid] == val)    
        {                 
            return mid+1;    
        }    
            /* if the item to be searched is smaller than middle, then it can only be in left subarray */  
        else if(a[mid] < val)     
        {  
            return binarySearch(a, mid+1, end, val);    
        }    
            /* if the item to be searched is greater than middle, then it can only be in right subarray */  
        else     
        {  
            return binarySearch(a, beg, mid-1, val);    
        }          
    }    
    return -1;     
}   
int main() {  
  int a[] = {11, 14, 25, 30, 40, 41, 52, 57, 70}; // given array  
  int val = 40; // value to be searched  
  int n = sizeof(a) / sizeof(a[0]); // size of array  
  int res = binarySearch(a, 0, n-1, val); // Store result  
  printf("The elements of the array are - ");  
  for (int i = 0; i < n; i++)  
  printf("%d ", a[i]);   
  printf("\nElement to be searched is - %d", val);  
  if (res == -1)  
  printf("\nElement is not present in the array");  
  else  
  printf("\nElement is present at %d position of array", res);  
  return 0;  
}  

// Iterative Solution : Time Complexity : O(LogN),  Aux. Space : O(1)

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int bSearch(int arr[], int n, int x)
	{
		int low = 0, high = n - 1;

		while(low <= high)
		{
			int mid = (low + high) / 2;

			if(arr[mid] == x)
				return mid;

			else if(arr[mid] > x)
				high = mid - 1;

			else
				low = mid + 1;
		}

		return -1;
	}

	public static void main(String args[]) 
	{
        int arr[] = {10, 20, 30, 40, 50, 60}, n = 6;

		int x = 25;
    
        System.out.println(bSearch(arr, n, x));  // Output : -1
		
    } 

}





// Recursive Solution : Time Complexity : O(LogN),  Aux. Space : O(logN)

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int bSearch(int arr[], int low, int high, int x)
	{
		if(low > high)
			return -1;

		int mid = (low + high) / 2;

		if(arr[mid] == x)
			return mid;

		else if(arr[mid] > x)
			return bSearch(arr, low, mid - 1, x);

		else
			return bSearch(arr, mid + 1, high, x);
	}

	public static void main(String args[]) 
	{
        int arr[] = {10, 20, 30, 40, 50, 60, 70}, n = 7;

		int x = 20;

        System.out.println(bSearch(arr, 0, n - 1, x));  // Output : 1
    } 
}

int firstOccurance(vector<int> &ar,int target){
  int low = 0,high = ar.size()-1,ans = -1;
  while(low<=high){
    int mid = low+(high-low)/2;
    
    if(ar[mid]==target){
      //mid can be our answer but we are not sure so reduce the search space
      ans = mid;
      high = mid-1;//for first occurance go to left
    }
    else if(ar[mid]>target)
      high = mid-1;
    else
      low = mid+1;
  }
  return ans;//if element is not present ans will remain -1,and will be returned as it is.
}

int lastOccurance(vector<int> &ar,int target){
  
  int low = 0,high = ar.size()-1,ans = -1;
  while(low<=high){
    int mid = low+(high-low)/2;
    
    if(ar[mid]==target){
      //mid can be our answer but we are not sure so reduce the search space
      ans = mid;
      low = mid+1; //for lasat occurance go to right
    }
    else if(ar[mid]>target)
      high = mid-1;
    else
      low = mid+1; 
  }
  
  return ans;//if element is not present ans will remain -1,and will be returned as it is.
}

//whenever there is sorted array first think of binary search

int binarySearch(vector<int> &ar, int target)
{

    int low = 0, high = ar.size() - 1;

    while (low <= high)
    {
        int mid = low + (high - low) / 2;

        if (ar[mid] == target)
            return mid;
        else if (ar[mid] > target)
            high = mid - 1; // go to left
        else
            low = mid + 1; // go to right
    }

    return -1; // if element is not found
}

//the above solution is only ,if array is sorted in ascending order
//for descending sorted array condition's to go to left and right reverse

//time complexity :- O(logn);