class Solution
{
public void printNos(int N)
{
//Your code
if(N==0) return;
printNos(N-1);
System.out.print(N+" ");
}
}
class Solution {
void printGfg(int N) {
for(int i = 0;i<N;i++){
System.out.print("GFG"+" ");
}
}
}
class Solution {
void printNos(int N) {
// code here
if(N ==0){
return;
}
printNos(N -1);
System.out.print(N+" ");
}
}
Problem
class Solution {
void printNos(int N) {
// code here
if(N ==0){
return;
}
System.out.print(N+" ");
printNos(N -1);
}
}
Problem
class Solution {
long sumOfSeries(long n) {
// code here
if(n == 0){
return 0;
}
return (long) Math.pow(n,3) + sumOfSeries(n-1);
}
}
Problem
class Solution {
static ArrayList<Long> factorialNumbers(long n) {
// code here
ArrayList<Long> list = new ArrayList<>();
long fact = 1;
for(long i = 1;i<=n;i++){
fact = fact * i;
if(fact<=n){
list.add(fact);
}
else {
break;
}
}
return list;
}
}
public class Main{
public static void printarray(int ans[],int size){
System.out.println("Array:");
for(int i = 0;i<size;i++){
System.out.print(ans[i]+" ");
}
}
public static void reversearr(int arr[],int size){
int ans[] = new int[size];{
for(int i = size - 1;i>=0;i--){
ans[size - i - 1] = arr[i];
}
printarray(ans,size);
}
}
public static void main (String[] args) {
int arr[] = {2,3,4,5,6};
int n = 5;
reversearr(arr,n);
}
}public class Main{
public static void main (String[] args) {
int arr[] = {1,2,3,4,6,7};
int n = 5;
revarrusingrec(arr,0,n - 1);
printarray(arr,n);
}
// reverse array using recursion method
public static void revarrusingrec(int arr[],int startindex,int endindex){
if(startindex<endindex){
// use swap method
int temporary = arr[startindex];
arr[startindex] = arr[endindex];
arr[endindex] = temporary;
revarrusingrec(arr,startindex + 1,endindex - 1);
}
}
// print it
public static void printarray(int arr[],int size){
System.out.println("Reverse Array:");
for(int i = 0;i<size;i++){
System.out.print(arr[i]+" ");
}
}
}
Problem
class Solution {
public boolean isPalindrome(String s) {
s = s.toLowerCase().replaceAll("[^A-Za-z0-9]","");
int fwd = 0;
int bwd= s.length()-1;
while(fwd<=bwd)
{
if(s.charAt(fwd) != s.charAt(bwd))
{
return false;
}
fwd = fwd + 1;
bwd = bwd - 1;
}
return true;
}
}
Problem
class Solution {
public int fib(int n) {
int sum = 0;
int sum1 = 1;
for(int i = 0;i<n;i++){
int sum2 = sum1 + sum;
sum = sum1;
sum1 = sum2;
}
return sum;
}
}
Algorithm: Brian's Kernighans
class Solution {
public boolean isPowerOfFour(int n)
{
if(n==1){
return true;
}
else if(n>1){
boolean containssinglebit = (n &(n-1))==0;
boolean fourorsixinzerobit = (n%10==4 || n%10==6);
return containssinglebit && fourorsixinzerobit;
}
else{
return false;
}
}
}
class Solution {
public boolean isPowerOfThree(int n) {
if( n < 1) return false;
while(n % 3 == 0){
n = n / 3;
}
return n == 1;
}
}
class Solution {
public int singleNumber(int[] nums) {
int len = nums.length;
int value = 0;
for(int i = 0;i<len;i++){
value = value^nums[i];
}
return value;
}
}
Problem
import java.util.*;
public class index{
public static void main(String[] args) {
Scanner S = new Scanner(System.in);
int n = 5;
int arr[] = new int[n];
for(int i = 0;i<arr.length;i++)
{
arr[i] = S.nextInt();
}
selection_sort(arr,n);
for(int i = 0;i<arr.length;i++){
System.out.println(arr[i]+" ");
}
S.close();
}
public static void selection_sort(int arr[],int n)
{
// int i,j,min_index,temp;
for(int i = 0;i<=n-1;i++){
int min_index = i;
for (int j = i+1;j<n;j++) {
if (arr[j]<arr[min_index])
{
min_index = j;
}
}
int temp = arr[min_index];
arr[min_index] = arr[i];
arr[i] = temp;
}
}
}class solution
{
int select(int arr[], int n)
{
// code here such that selectionSort() sorts arr[]
return arr[n];
}
void selectionSort(int arr[], int n)
{
//code here
Arrays.sort(arr);
for(int i = 0;i<n;i++){
select(arr,i);
}
}
}
import java.util.*;
class solution
{
public static void main(String args[])
{
Scanner S = new Scanner(System.in);
int size = S.nextInt();
int arr[] = new int[size];
for(int i = 0;i<size;i++){
arr[i] = S.nextInt();
}
bubblesort(arr,size);
for(int j = 0;j<arr.length;j++)
{
System.out.print(arr[j] +" ");
}
}
static void bubblesort(int arr[],int n){
for(int i = n - 1;i>=1;i--)
{
int didswap = 0;
for(int j = 0;j<=i - 1;j++)
{
if(arr[j]>arr[j+ 1]){
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
didswap = 1;
}
}
if(didswap == 0){
break;
}
}
}
}class solution
{
int bubble(int arr[], int n)
{
// code here such that bubbleSort() sorts arr[]
return arr[n];
}
void bubbleSort(int arr[], int n)
{
//code here
Arrays.sort(arr);
for(int i = 0;i<n;i++){
select(arr,i);
}
}
}
Problem
import java.util.*;
class solution
{
public static void main(String args[])
{
Scanner S = new Scanner(System.in);
int size = S.nextInt();
int arr[] = new int[size];
for(int i = 0;i<size;i++){
arr[i] = S.nextInt();
}
insertionsort(arr,size);
}
static void insertionsort(int arr[],int size){
for(int i = 0;i<arr.length;i++)
{
int j = i;
while(j>0 && arr[j - 1] > arr[j])
{
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
j--;
System.out.print("ret"+" ");
}
}
}
}class solution
{
int insert(int arr[], int n)
{
// code here such that InsertionSort sorts arr[]
return arr[n];
}
void Insertionsort(int arr[], int n)
{
//code here
Arrays.sort(arr);
for(int i = 0;i<n;i++){
insert(arr,i);
}
}
}
public static void mergeSort(int[] arr, int numberOfElements) {
if (numberOfElements < 2) {
return;
}
// Find the middle position and create left and right partitions
int mid = numberOfElements/2;
int[] leftArr = new int[mid];
int[] rightArr = new int[numberOfElements - mid];
// Fill up the partitions
for (int i = 0; i < mid; i++) {
leftArr[i] = arr[i];
}
for (int i = mid; i < numberOfElements; i++) {
rightArr[i- mid] = arr[i];
}
// Apply merge sort on the left parition
mergeSort(leftArr, mid);
// Apply merge sort on the right partition
mergeSort(rightArr, numberOfElements - mid);
// Finally merge the partitions
merge(arr, leftArr, rightArr, mid, numberOfElements - mid);
}
private static void merge(int[] arr, int[] leftArr, int[] rightArr, int left, int right) {
int i = 0, j = 0, k = 0;
// Merge arrays based on the smaller values
while (i < left && j < right) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
}
else {
arr[k++] = rightArr[j++];
}
}
// Fill out remaining values if any
while (i < left) {
arr[k++] = leftArr[i++];
}
while (j < right) {
arr[k++] = rightArr[j++];
}
}
public static void quickSort(int[] arr, int begin, int end) {
if (begin < end) {
// Find the partition
int partition = findPartition(arr, begin, end);
// Do quick sort on the left part
quickSort(arr, begin, partition - 1);
// Do quick sort on the right part
quickSort(arr, partition + 1, end);
}
}
private static int findPartition(int[] arr, int begin, int end) {
// Taking last element as pivot element
int pivot = arr[end];
int i = (begin - 1); // index of smaller element
for (int j = begin; j < end; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
i++;
// swap arr[i] and arr[j]
swap(arr, i, j);
}
}
// swap arr[i+1] and arr[high] (or pivot)
swap(arr, i + 1, end);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int swapTemp = arr[i];
arr[i] = arr[j];
arr[j] = swapTemp;
}Arrays.sort(arr);
Problem
class Solution {
public static int largest(int n, int[] arr) {
// code here
int larg = arr[0];
for(int i = 0;i<n;i++){
if(arr[i]>larg){
larg = arr[i];
}
}
return larg;
}
}
Problem
class Solution {
public int print2largest(List<Integer> arr) {
// Code Here
Collections.sort(arr);
int n = arr.size();
if(n<2){
return -1;
}
int x = arr.get(n - 1);
for(int i = n - 2;i>=0;i--){
if(arr.get(i) != x){
return arr.get(i);
}
}
return -1;
}
}import java.util.*;
class solution{
public static int secondlargest(int arr[],int n){
int n = arr.length;
if(n == 0 || n==1){
return -1;
}
Arrays.sort(arr);
int largest = arr[n - 2];
System.out.println(largest);
}import java.util.*;
public class solution{
public static int secondlargest(int arr[],int n){
int firstlargest = arr[n - 1];
int seconlrgt = 0;
for(int i = n - 2;i>=0;i--){
if(arr[i] != firstlargest){
secondlrgt = arr[i];
break;
}
}
System.out.println(secondlrgt);
}
}* Brute Force Pseudocode
* Better Approach pseudocode
class Solution {
public boolean check(int[] nums) {
int count = 0;
for(int i = 0;i<nums.length;i++){
if(nums[i] > nums[(i+1) % nums.length]){
count++;
}
}
if(count > 1){
return false;
}
return true;
}
}class Solution {
public boolean check(int[] nums) {
int count = 0;
for(int i = 1;i<nums.length;i++){
if(nums[i] > nums[(i+1)])
return false;
}
return true;
}
class Solution {
public int removeDuplicates(int[] nums) {
int len = nums.length;
int i = 0;
for(int j = 0;j<len;j++){
if(nums[j] != nums[i]){
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
}
class solution{
public void rotatesinglearray(int arr[],int k){
int temp = arr[0];
for(int i = 1;i<k;i++){
arr[i - 1] = arr[i];
}
int lastindex = temp;
return arr;
}
class Solution {
public void rotate(int[] nums, int k) {
k = k%nums.length;
// reverse an array
reverse(nums,0,nums.length - 1);
// reverse an array up to the index k;
reverse(nums,0,k - 1);
//reverse an array after k up to endindex;
reverse(nums,k,nums.length - 1);
}
public void reverse(int[] nums,int startindex,int endindex){
while(startindex<endindex){
int temp = nums[startindex];
nums[startindex] = nums[endindex];
nums[endindex] = temp;
startindex++;
endindex--;
}
}
}
class Solution {
public void moveZeroes(int[] nums) {
//array length
int len = nums.length;
// array check for base case;
if(len<2){
return;
}
int slow = 0;
int fast = 0;
while(fast < len){
if(nums[fast] != 0){
int temp = nums[fast];
nums[fast] = nums[slow];
nums[slow] = temp;
slow++;
fast++;
}
else{
fast++;
}
}
}
}
class Solution {
static int searchInSorted(int arr[], int N, int K) {
for(int i = 0;i<N;i++){
if(arr[i] == K){
return 1;
}
}
return -1;
// Your code here
}
}
class Solution
{
//Function to return a list containing the union of the two arrays.
public static ArrayList<Integer> findUnion(int arr1[], int arr2[], int n, int m)
{
// add your code here
Set<Integer> result = new TreeSet<>();
for(int i : arr1){
result.add(i);
}
for(int j : arr2){
result.add(j);
}
return new ArrayList<>(result);
}
}
class Solution {
public int missingNumber(int[] nums) {
int sums = 0;
for(int i = 0;i<nums.length;i++){
sums = sums + nums[i];
}
int actualsum = (nums.length * (nums.length + 1))/2;
int res = actualsum - sums;
return res;
}
}
C++
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int maxi = 0;
int count = 0;
for(int i = 0;i<nums.size();i++){
if(nums[i] == 1){
count++;
maxi = max(maxi,count);
}
else{
count = 0;
}
}
return maxi;
}
};Java
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int maxi = 0;
int count = 0;
for(int i = 0;i<nums.length;i++){
if(nums[i] == 1){
count++;
maxi = Math.max(count,maxi);
}
else{
count = 0;
}
}
return maxi;
}
}
class Solution {
// Function for finding maximum and value pair
public static int lenOfLongSubarr(int A[], int N, int K) {
// Complete the function
HashMap<Integer,Integer> prevsum = new HashMap<>();
int sum = 0,maxlen = 0;
for(int i = 0;i<N;i++){
sum = sum + A[i];
if(sum == K){
maxlen = i + 1;
}
if(!prevsum.containsKey(sum)){
prevsum.put(sum, i);
}
if(prevsum.containsKey(sum - K)){
maxlen = Math.max(maxlen, i - prevsum.get(sum - K));
}
}
return maxlen;
}
}
class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
int res = 0;
for(int row = 0;row<len;row++){
for(int col = row + 1;col<len;col++){
if(nums[row] + nums[col] == target){
return new int[]{row,col};
}
}
}
return new int[]{};
}
}
class Solution {
public void sortColors(int[] nums) {
int len = nums.length;
Arrays.sort(nums);
for(int i = 0;i<len;i++){
System.out.println(nums[i]);
}
}
}
class Solution {
public int majorityElement(int[] nums) {
//arraylength
int len = nums.length;
//count
int count = 1;
//majority element
int majority = nums[0];
// check majority
for(int i = 0;i<len;i++){
if(nums[i] == majority){
count = count + 1;
}
else{
count = count - 1;
if(count == 0){
majority = nums[i];
count = 1;
}
}
}
return majority;
}
}
class Solution {
public int maxSubArray(int[] nums) {
// length
int len = nums.length;
// sum
int sum = 0;
// max sum
int max_sum = nums[0];
// check using kadane Algorithm
for(int i = 0;i<len;i++){
sum = sum + nums[i];
max_sum = Math.max(max_sum,sum);
if(sum<0){
sum = 0;
}
}
return max_sum;
}
}
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
for(int i = digits.size() - 1;i>=0;i--){
if(digits[i]<9){
digits[i]++;
return digits;
}
else{
digits[i] = 0;
}
}
digits.push_back(0);
digits[0] = 1;
return digits;
}
};class Solution {
// Function to find pair with maximum sum
public int pairWithMaxSum(List<Integer> arr) {
// Your code goes here
int max = 0;
int sum = 0;
for(int i = 0;i<arr.size() - 1;i++){
sum = arr.get(i) + arr.get(i + 1);
max = Math.max(sum,max);
}
return max;
}
}
class Solution {
public int maxProfit(int[] prices) {
//at the beginning the minimum is the first place
int buy_price = prices[0];
// profit
int profit = 0;
for(int i = 1;i<prices.length;i++){
// if current price is less than buy_price
if(prices[i]<buy_price){
buy_price = prices[i];
}
else{
// else check if we can get better profit
int current_profit = prices[i] - buy_price;
profit = Math.max(current_profit,profit);
}
}
return profit;
}
}
class Solution {
public int[] rearrangeArray(int[] nums) {
int len = nums.length;
int positive = 0;
int negative = 1;
int[] fin = new int[len];
for(int i = 0;i<len;i++){
if(nums[i] < 0){
fin[negative] = nums[i];
negative = negative + 2;
}
else{
fin[positive] = nums[i];
positive = positive + 2;
}
}
return fin;
}
}class Solution {
public int subarraySum(int[] nums, int k) {
int n=0;
for(int i=0; i<nums.length; i++)
{
int s=0;
for(int j=i; j<nums.length; j++)
{
s+=nums[j];
if(s==k)
n++;
}
}
return n;
}
}class Solution {
// Function to find the leaders in the array.
static ArrayList<Integer> leaders(int n, int arr[]) {
// Your code here
// new arraylist
ArrayList<Integer> list = new ArrayList<>();
// max
int max = arr[n - 1];
// the value from reverse to check max
for(int first = n - 1;first>=0;first--)
{
if(arr[first] >= max)
{
list.add(0,arr[first]);
max = arr[first];
}
}
return list;
}
}
class Solution {
public int longestConsecutive(int[] nums) {
int n = nums.length;
if (n == 0)
return 0;
int longest = 1;
Set<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) {
set.add(nums[i]);
}
for (int i : set) {
if (!set.contains(i - 1)) {//check if 'i' is a starting number
int cnt = 1;
int tempIndex = i;
while (set.contains(tempIndex + 1)) {
tempIndex++;
cnt++;
}
longest = Math.max(longest, cnt);
}
}
return longest;
}
class Solution {
public void rotate(int[][] matrix) {
for(int i = 0;i<matrix.length;i++){
for(int j = 0;j<i;j++){
// swap the values using two pointer
int temporary = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temporary;
}
}
for(int i = 0;i<matrix.length;i++){
for(int j = 0;j<matrix.length/2;j++){
// swap the values using two pointer with last value of row
int temporary = matrix[i][j];
matrix[i][j] = matrix[i][matrix.length-1-j];
matrix[i][matrix.length-1-j] = temporary;
}
}
}
}
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int rowlen = matrix.length;//row length
int collen = matrix[0].length; //col length
int left = 0;
int right = collen - 1;
int top = 0;
int bottom = rowlen -1;
List<Integer> list = new ArrayList<>();
while(top<=bottom && left<=right)
{
// left to right
for(int i = left;i<=right;i++){
list.add(matrix[top][i]);
}
top++;
// top to bottom
for(int i = top;i<=bottom;i++){
list.add(matrix[i][right]);
}
right--;
// right to left (if still top is need to be less than bottom)
if(top <= bottom){
for(int i = right;i>=left;i--){
list.add(matrix[bottom][i]);
}
}
bottom--;
// bottom to top
if(left<= right){
for(int i = bottom;i>=top;i--){
list.add(matrix[i][left]);
}
}
left++;
}
return list;
}
} class Solution {
public void setZeroes(int[][] matrix) {
boolean firstrow = false,firstcolumn = false;
// set markers in first row and first column
for(int i = 0;i<matrix.length;i++)
{
for(int j = 0;j<matrix[0].length;j++){
if(matrix[i][j] == 0){
if(i == 0){
firstrow = true;
}
if(j == 0){
firstcolumn = true;
}
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
// replace inner matrix
for(int i = 1;i<matrix.length;i++){
for(int j = 1;j<matrix[0].length;j++){
if(matrix[i][0] == 0 || matrix[0][j] == 0){
matrix[i][j] = 0;
}
}
}
if(firstrow){
for(int j = 0;j<matrix[0].length;j++){
matrix[0][j] = 0;
}
}
if(firstcolumn){
for(int i = 0;i<matrix.length;i++){
matrix[i][0] = 0;
}
}
}
}
class Solution {
public void nextPermutation(int[] nums) {
int ind1=-1;
int ind2=-1;
// step 1 find breaking point
for(int i=nums.length-2;i>=0;i--){
if(nums[i]<nums[i+1]){
ind1=i;
break;
}
}
// if there is no breaking point
if(ind1==-1){
reverse(nums,0);
}
else{
// step 2 find next greater element and swap with ind2
for(int i=nums.length-1;i>=0;i--){
if(nums[i]>nums[ind1]){
ind2=i;
break;
}
}
swap(nums,ind1,ind2);
// step 3 reverse the rest right half
reverse(nums,ind1+1);
}
}
void swap(int[] nums,int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
void reverse(int[] nums,int start){
int i=start;
int j=nums.length-1;
while(i<j){
swap(nums,i,j);
i++;
j--;
}
}
}
function pascalTriangle(n) {
let ans = 1;
console.log(ans + " "); // printing 1st element
//Printing the rest of the part:
for (let i = 1; i < n; i++) {
ans = ans * (n - i);
ans = ans / i;
console.log(ans + " ");
}
console.log("n");
}
const n = 5;
pascalTriangle(n);
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> result = new ArrayList<>();
Set<Integer> uniqueNums = new HashSet<>();
for (int num : nums) {
uniqueNums.add(num);
}
for (int num : uniqueNums) {
int count = 0;
for (int n : nums) {
if (n == num) {
count++;
}
}
if (count > nums.length / 3) {
result.add(num);
}
}
return result;
}
}
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// check list length or null
if(nums == null || nums.length < 3){
return new ArrayList<>();
}
// sort
Arrays.sort(nums);
// set
Set<List<Integer>> result = new HashSet<>();
// using two pointers
for(int i = 0;i<nums.length - 2;i++)
{
int left = i + 1;
int right = nums.length - 1;
while(left < right)
{
// sum nums values
int sum = nums[i] + nums[left] + nums[right];
//if sum is equal to zero
if(sum == 0)
{
result.add(Arrays.asList(nums[i],nums[left],nums[right]));
left++;
right--;
}
else if(sum < 0)
{
left++;
}
else
{
right--;
}
}
}
return new ArrayList<>(result);
}
}class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
int size = nums.length;
if (nums == null || size < 4) {
return result;
}
Arrays.sort(nums);
for (int i = 0; i < size - 3; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue;
for (int j = i + 1; j < size - 2; j++) {
if (j > i + 1 && nums[j] == nums[j-1]) continue;
int left = j + 1, right = size - 1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
List<Integer> res = new ArrayList<>();
res.add(nums[i]); res.add(nums[j]); res.add(nums[left]); res.add(nums[right]);
result.add(res);
left++;
right--;
while (left < right && nums[left] == nums[left-1]) {
left++;
}
while (left < right && nums[right] == nums[right+1]) {
right--;
}
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return result;
}
}
class Solution {
public int maxProduct(int[] nums) {
int len = nums.length;
int leftproduct = 1;
int rightproduct = 1;
int ans = nums[0];
for(int i = 0;i<len;i++){
if(leftproduct == 0){
leftproduct = 1;
}
if(rightproduct == 0){
rightproduct = 1;
}
//leftproduct
leftproduct = leftproduct * nums[i];
//rightproduct
rightproduct = rightproduct * nums[len - 1 - i];
ans = Math.max(ans,Math.max(leftproduct,rightproduct));
}
return ans;
}
}
for (int j = 0, i = m; j < n; j++) {
nums1[i] = nums2[j];
i++;
}
Arrays.sort(nums1);
import java.util.HashMap;
class Solution {
public int maxLen(int[] arr, int n) {
// Your code here
HashMap<Integer, Integer> mp = new HashMap<>();
int sum = 0;
int ans = 0;
mp.put(0, -1);
for (int i = 0; i < n; i++) {
sum += arr[i];
if (mp.containsKey(sum)) {
ans = Math.max(ans, i - mp.get(sum));
} else {
mp.put(sum, i);
}
}
return ans;
}
}class Solution {
public int arraySign(int[] nums) {
double result = 1;
for(int i = 0;i<nums.length;i++){
result = result * nums[i];
}
if(result < 0){
return -1;
}
else if(result > 0){
return 1;
}
else{
return 0;
}
}
}
public static int binarySearch(int[] nums, int target) {
int n = nums.length; //size of the array.
int low = 0, high = n - 1;
// Perform the steps:
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] == target) return mid;
else if (target > nums[mid]) low = mid + 1;
else high = mid - 1;
}
return -1;
}
} 
class Solution {
// Function to find floor of x
// arr: input array
// n is the size of array
static int findFloor(long arr[], int n, long x) {
int low=0,high=arr.length-1,ans=-1;
while(low <= high){
int mid=(low+high)/2;
if(arr[mid] == x) return mid;
else if(arr[mid] <= x){
ans = mid;
low=mid+1;
}else{
high=mid-1;
}
}
return ans;
}
}
class Solution {
// Function to find floor of x
// arr: input array
// n is the size of array
static int findFloor(long arr[], int n, long x) {
int low=0,high=arr.length-1,ans=-1;
while(low <= high){
int mid=(low+high)/2;
if(arr[mid] == x) return mid;
else if(arr[mid] < x){
ans = mid;
low=mid+1;
}else{
high=mid-1;
}
}
return ans;
}
}
class Solution {
public int searchInsert(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
int ans = nums.length;
while(low<=high){
int mid = (low + high)/2;
if(nums[mid] >= target){
ans = mid;
high = mid - 1;
}
else{
low = mid + 1;
}
}
return ans;
}
}
class Solution {
public int[] searchRange(int[] nums, int target) {
// first
int first = firstoccurence(nums,target);
// last
int last = lastoccurence(nums,target);
return new int[]{first,last};
}
public static int firstoccurence(int[] nums,int target){
int low = 0;
int high = nums.length - 1;
int first = -1;
while(low<=high){
int mid = (low + high)/2;
if(nums[mid] == target){
first = mid;
high = mid - 1;
}
else if(nums[mid]<target){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return first;
}
public static int lastoccurence(int[] nums,int target){
int low = 0;
int high = nums.length - 1;
int last = -1;
while(low<=high){
int mid = (low + high)/2;
if(nums[mid] == target){
last = mid;
low = mid + 1;
}
else if(nums[mid]<target){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return last;
}
}
class Solution {
int count(int[] arr, int n, int x) {
// code here
int count = 0;
for(int i = 0;i<n;i++){
if(arr[i] == x){
count++;
}
}
return count;
}
}
class Solution {
public int search(int[] nums, int target) {
int ans = -1;
for(int i = 0;i<nums.length;i++){
if(nums[i] == target){
ans = i;
}
}
return ans;
}
}class Solution {
public boolean search(int[] nums, int target) {
boolean ans = true;
for(int i = 0;i<nums.length;i++){
if(nums[i] == target){
return ans;
}
}
return false;
}
}class Solution {
public int findMin(int[] nums)
{
Arrays.sort(nums);
int min = nums[0];
for(int i = 0;i<nums.length;i++){
if(nums[i]<min){
min = i;
}
}
return min;
}
}
public int findKRotation(List<Integer> arr) {
// Code here
int low=0;
int high=arr.size()-1;
int ans=Integer.MAX_VALUE;
int index=-1;
while(low<=high){
int mid=(low+high)/2;
if(arr.get(low)<=arr.get(high)){
if(arr.get(low)<ans){
index=low;
ans=arr.get(low);
}
break;
}
//left part sorted.
if(arr.get(low)<=arr.get(mid)){
if(arr.get(low)<ans){
index=low;
ans=arr.get(low);
}
low=mid+1;
}
else{
//right part sorted.
if(arr.get(mid)<ans){
index=mid;
ans=arr.get(mid);
}
high=mid-1;
}
}
return index;
}
class Solution {
public int singleNonDuplicate(int[] nums) {
int res = 0;
for(int ans : nums){
res = res ^ ans;
}
return res;
}
}class Solution {
public int singleNonDuplicate(int[] nums) {
int n = nums.length;
int left = 0;
int right = n - 1; // Fix the initial value of right
while (left <= right) {
int mid = (left + right) / 2;
// Check if mid is the single element by verifying its neighbors, ensuring mid is not at the boundary
if ((mid == 0 || nums[mid] != nums[mid - 1]) && (mid == n - 1 || nums[mid] != nums[mid + 1])) {
return nums[mid];
}
// Adjust binary search range based on even/odd index and matching conditions
if ((mid % 2 == 0 && nums[mid] == nums[mid + 1]) || (mid % 2 == 1 && nums[mid] == nums[mid - 1])) {
left = mid + 1; // Single element is in the right half
} else {
right = mid - 1; // Single element is in the left half
}
}
return -1; // Shouldn't reach here as there is always one non-duplicate element
}
}#include <vector>
#include <limits.h>
class Solution {
public:
int findPeakElement(std::vector<int>& nums) {
int len = nums.size();
if (len == 1) {
return 0;
}
int max = INT_MIN, req = 0, res = 0;
for (int i = 0; i < len; i++) {
if (nums[i] > max) {
max = nums[i];
res = i;
req = 1;
}
}
if (req == 1) {
return res;
} else {
return 0;
}
}
};class Solution {
long floorSqrt(long n) {
return (long)(Math.floor(Math.pow(n , 0.5)));
}
}class Solution
{
public int NthRoot(int n, int m)
{
// code here
int l=0;
int r=m;
while(l<=r){
int mid=(l+r)/2;
if(Math.pow(mid,n) == m){
return mid;
}
else if(Math.pow(mid,n) < m){
l=mid+1;
}
else{
r=mid-1;
}
}
return -1;
}
class Solution {
public int findKthPositive(int[] arr, int k) {
int low = 0,high = arr.length - 1;
while(low<=high){
int mid = (low + high)/2;
int misnum = arr[mid] - (mid + 1);
if(misnum < k){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return k + high + 1;
}
}class Solution {
public long kthElement(int k, int arr1[], int arr2[]) {
// code here
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0;i<arr1.length;i++){
list.add(arr1[i]);
}
for(int i = 0;i<arr2.length;i++){
list.add(arr2[i]);
}
Collections.sort(list);
return list.get( k - 1);
}
}
class Solution {
public int smallestDivisor(int[] nums, int threshold) {
Arrays.sort(nums);
int low = 1,high = nums[nums.length - 1],ans = 1;
while(low <= high){
int mid = (low + high) / 2;
int sum = 0;
for(int i = 0;i<nums.length;i++)
{
sum = sum + (int) Math.ceil((double)nums[i] / (double)mid);
}
if(sum<=threshold){
ans = mid;
high = mid - 1;
}
else{
low = mid + 1;
}
}
return ans;
}
}
class Solution {
public int shipWithinDays(int[] weights, int D)
{
// minimum capacity
int minCap = 0;
// maximum capacity
int maxCap = 0;
for (int weight : weights)
{
minCap = Math.max(minCap, weight);
maxCap += weight;
}
// Apply binary search
while (minCap < maxCap) {
int mid = minCap + (maxCap - minCap) / 2;
// Try to ship with "mid" capacity
int days = 1;
int sum = 0;
for (int weight : weights) {
if (sum + weight > mid) {
days++;
sum = 0;
}
sum += weight;
}
// If more days are required, increase capacity
if (days > D)
minCap = mid + 1;
else
maxCap = mid;
}
return minCap;
}
}
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n1 = nums1.length,n2 = nums2.length;
int i = 0,j = 0;
int n = n1 + n2;
// index2
int ind2 = n / 2;
// index1
int ind1 = ind2 - 1;
// count
int count = 0;
// index element 1
int ind1el = -1;
// index element 2
int ind2el = -1;
// running loops
while(i < n1 && j < n2)
{
// nums1 is less than nums2
if(nums1[i] < nums2[j])
{
// index1 is equalto count
if(count == ind1){
ind1el = nums1[i];
}
// index1 is equato count
if(count == ind2){
ind2el = nums1[i];
}
count++;
i++;
}
// nums2 is less than nums1
else{
// index1 is equalto count
if(count == ind1){
ind1el = nums2[j];
}
// index1 is equato count
if(count == ind2){
ind2el = nums2[j];
}
count++;
j++;
}
}
while (i<n1)
{
// index1 is equalto count
if(count == ind1){
ind1el = nums1[i];
}
// index1 is equato count
if(count == ind2){
ind2el = nums1[i];
}
count++;
i++;
}
while( j<n2)
{
// index1 is equalto count
if(count == ind1){
ind1el = nums2[j];
}
// index1 is equato count
if(count == ind2)
{
ind2el = nums2[j];
}
count++;
j++;
}
if(n %2 == 1){
return ind2el;
}
return (double)((double)(ind1el + ind2el)) / 2.0;
}
}
#include<bits/stdc++.h>
int countstudents(vector<int> &arr,int pages){
int students = 1;
long long pagestudent = 0;
for(int i = 0;i<arr.size();i++){
if(pagestudent + arr[i] <= pages){
pagestudent += arr[i];
}
else{
students = students + 1;
pagestudent = arr[i];
}
}
return students;
}
int findPages(vector<int>& arr, int n, int m) {
// Write your code here.
if(m>n) return -1;
int low = *max_element(arr.begin(),arr.end());
int high = accumulate(arr.begin(),arr.end(),0);
while(low <= high){
int mid = (low+high)/2;
int students = countstudents(arr,mid);
if(students>m){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return low;
}
#include<bits/stdc++.h>
int countstudents(vector<int> &arr,int pages){
int students = 1;
long long pagestudent = 0;
for(int i = 0;i<arr.size();i++){
if(pagestudent + arr[i] <= pages){
pagestudent += arr[i];
}
else{
students = students + 1;
pagestudent = arr[i];
}
}
return students;
}
int findPages(vector<int>& arr, int n, int m) {
// Write your code here.
if(m>n) return -1;
int low = *max_element(arr.begin(),arr.end());
int high = accumulate(arr.begin(),arr.end(),0);
while(low <= high){
int mid = (low+high)/2;
int students = countstudents(arr,mid);
if(students>m){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return low;
}
int findLargestMinDistance(vector<int> &arr, int k)
{
// Write your code here.
return findPages(arr,arr.size(),k);
}
class Solution {
public int rowWithMax1s(int arr[][])
{
int ans = -1;
int max = 0;
for(int i = 0;i< arr.length;i++)
{
int count = 0;
for(int j = 0;j<arr[i].length;j++)
{
if(arr[i][j] == 1){
count = count + 1;
}
}
if(count > max){
max = count;
ans = i;
}
}
return ans;
}
}class Solution {
searchMatrix(matrix, target) {
let ans = true;
for (let m = 0; m < matrix.length; m++) {
for (let n = 0; n < matrix[m].length; n++) {
if (matrix[m][n] === target) {
return ans;
}
}
}
return false;
}
}class Solution {
searchMatrix(matrix, target) {
let ans = true;
for (let m = 0; m < matrix.length; m++) {
for (let n = 0; n < matrix[m].length; n++) {
if (matrix[m][n] === target) {
return ans;
}
}
}
return false;
}
}class Solution {
public int[] findPeakGrid(int[][] matrix) {
// using binary search
int low = 0;
int high = matrix[0].length - 1;
while(low <= high){
// mid value
int mid = (low+high) / 2;
int row = maxiele(matrix,mid);
int left = mid - 1>=0 ? matrix[row][mid - 1] : -1;
int right = mid + 1< matrix[0].length?matrix[row][mid+1] : -1;
if(matrix[row][mid]>left&&matrix[row][mid]>right) {
return new int[]{row,mid};
}
else if(matrix[row][mid]<left) {
high=mid-1;
}
else {
low=mid+1;
}
}
return new int[]{-1,-1};
}
// to find maximum element
public int maxiele(int[][] array,int column){
// max element
int max = Integer.MIN_VALUE;
int row = -1;
for(int m = 0;m<array.length;m++){
if(max<array[m][column]){
max = array[m][column];
row = m;
}
}
return row;
}
}
class Solution {
public char findTheDifference(String s, String t) {
int total = 0;
for(int i = 0;i<t.length();i++){
total = total + t.charAt(i);
}
for(int i = 0;i<s.length();i++){
total = total - s.charAt(i);
}
return (char)total;
}
}class Solution {
public:
string mergeAlternately(string word1, string word2) {
//two pointers
int i = 0;
int j = 0;
// empty string
string res = "";
// size
while(i<word1.size() && j<word2.size()){ // size from 0 to length of word
res += word1[i++];
res += word2[j++];
}
// i
while(i<word1.size()){
res += word1[i++];
}
// j
while(j<word2.size()){
res += word2[j++];
}
return res;
}
};class Solution {
public int strStr(String haystack, String needle) {
for(int i = 0;i<haystack.length() - needle.length() + 1;i++){
if(haystack.charAt(i) == needle.charAt(0)){
if(haystack.substring(i,needle.length() + i).equals(needle)){
return i;
}
}
}
return -1;
}
}class Solution {
public boolean isAnagram(String s, String t) {
// length
if(s.length() != t.length())return false;
//change to charArray
char a[] = s.toCharArray();
char b[] = t.toCharArray();
// sort
Arrays.sort(a);
Arrays.sort(b);
// check value
for(int i = 0;i<a.length;i++){
if(a[i]!=b[i]){
return false;
}
}
return true;
}
}
class Solution
{
public boolean rotateString(String s, String goal) {
return (s.length() == goal.length() && (s+s).contains(goal));
}
}class Solution {
public boolean isIsomorphic(String s, String t) {
// create array to store index of characters in both strings
int[] indexs = new int[200];
int[] indext = new int[200];
// if the length is not equal then return false
if(s.length() != t.length()){
return false;
}
//iterate through each charaters
for(int i = 0;i<s.length();i++){
if(indexs[s.charAt(i)] != indext[t.charAt(i)]){
return false;
}
indexs[s.charAt(i)] = i + 1;
indext[t.charAt(i)] = i + 1;
}
return true;
}
}
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
if (strs.length == 1) {
return strs[0];
}
int prefixEnd = 0;
while (true) {
for (int i = 0; i < strs.length - 1; i++) {
if (prefixEnd >= strs[i].length() || prefixEnd >= strs[i+1].length())
return strs[0].substring(0, prefixEnd);
if (strs[i].charAt(prefixEnd) != strs[i + 1].charAt(prefixEnd))
return strs[0].substring(0, prefixEnd);
}
prefixEnd++;
}
}
}class Solution {
public String largestOddNumber(String num) {
if(num.length() == 0) return "";
for(int i = num.length() - 1;i>=0;i--){
char res = num.charAt(i);
if(res % 2 == 1){
return num.substring(0,i+1);
}
}
return "";
}
}class Solution {
public String largestGoodInteger(String num) {
String[] sequences = {"999", "888", "777", "666", "555", "444", "333", "222", "111", "000"};
for (String seq : sequences) {
if (num.contains(seq)) {
return seq;
}
}
return "";
}
}class Solution {
public String removeOuterParentheses(String s) {
StringBuilder str = new StringBuilder();
int cnt = 0;
char[] ch = s.toCharArray();
int n = ch.length;
for(int i = 1; i < n; ++i) {
if(ch[i] == '(') {
cnt++;
str.append('(');
}
else {
if(cnt == 0) i++;
else {
cnt--;
str.append(')');
}
}
}
return str.toString();
}
}
class Solution {
public String reverseWords(String s) {
String[] arr = s.split(" +"); // use split function and regex
StringBuilder res = new StringBuilder();
for(int index = arr.length - 1;index>=0;index--){
res.append(arr[index]);
res.append(" ");
}
return res.toString().trim();
}
}class Solution {
public int maxDepth(String s) {
int soln = 0,count = 0;
for(char req : s.toCharArray()){
if(req == '('){
count++;
}
else if(req == ')'){
count--;
}
soln = Math.max(soln,count);
}
return soln;
}
}
class Solution {
public int romanToInt(String s) {
Map<Character, Integer> ans = new HashMap<>();
ans.put('I',1);
ans.put('V',5);
ans.put('X',10);
ans.put('L',50);
ans.put('C',100);
ans.put('D',500);
ans.put('M',1000);
int result = ans.get(s.charAt(s.length() - 1));
for(int i = s.length() - 2;i>=0;i--){
if(ans.get(s.charAt(i)) < ans.get(s.charAt(i + 1))){
result = result - ans.get(s.charAt(i));
}
else{
result = result + ans.get(s.charAt(i));
}
}
return result;
}
}class Solution {
public int lengthOfLastWord(String s) {
s = s.trim();
int count = 0;
for(int index = s.length() - 1;index >= 0;index--){
if(s.charAt(index) == ' '){
break;
}
count = count + 1;
}
return count;
}
}long long int myAtoi(char* s) {
long long int i=0,sum=0,f=0;
char si='+';
while(s[i]!='\0')
{
if(s[i]=='-'&&f==0)
{
si='-';
f=1;
}
else if(s[i]=='+'&&f==0)
{
si='+';
f=1;
}
else if(s[i]==' '&&f==0)
{
}
else if(s[i]>='0'&&s[i]<='9')
{
if(sum>INT_MAX)
{
goto z;
}
sum=sum*10+(s[i]-'0');
if(!isdigit(s[i+1]))
{
break;
}
}
else
{
break;
}
i++;
}
z:
if(si=='-')
{
sum*=-1;
if(sum<INT_MIN)
{
return INT_MIN;
}
return sum;
}
else
{
if(sum>INT_MAX)
{
return INT_MAX;
}
return sum;
}
}class Solution {
public int l = 0;
public int r = 0;
public void func(char[] ch, int i) {
if (i >= ch.length) return;
int s = i;
int e = i;
while (e < ch.length - 1 && ch[e] == ch[e + 1]) e++;
i=e;
while (s >= 0 && e < ch.length && ch[s] == ch[e]) {
s--;
e++;
}
s++;
e--;
if (e - s > r - l) {
r = e;
l = s;
}
func(ch, i + 1);
}
public String longestPalindrome(String s) {
char[] ch = s.toCharArray();
func(ch, 0);
return s.substring(l, r + 1);
}
}
class Node{
int data;
Node next;
// linkedlist starts.
Node(int data1,Node next1){
this.data = data1;
this.next = next1;
}
//linkedlist ends.
Node(int data1){
this.data = data1;
this.next = null;
}
}
public class Main
{
public static void main(String[] args) {
System.out.println("linked list");
int arr[] = {2,4,5,2,24,2};
Node av = new Node(arr[2]);
System.out.println(av.data);
}
}private class LL
{
private Node head;
private Node tail;
class Node
{
// reference variables
private int value;
private Node data;
// constructor
public Node(int value){
this.value = value;
}
public Node(int value,Node node){
this.value = value;
this.node = node;
}
}
// size
private int size;
// constructor
public LL(){
this.size = 0;
}
public void insert(int value){
Node node = new Node(value);
node.next = head;
head = node;
if(tail == null){
tail = head;
}
size++;
}
}
public class Main
{
public static void main(String args[])
{
LL list = new LL();
}
}class Solution {
static Node constructLL(int[] arr) {
// code here
// null
Node ptr = new Node(0);
// assign head as array first value
Node head = new Node(arr[0]);
ptr = head;
for(int i = 1;i<arr.length;i++){
Node temp = new Node(arr[i]);
ptr.next = temp;
ptr = temp;
}
return head;
}
}