Fixes.

omprashantjain · omprashantjain · commit 1984deb080c4 · 2024-04-26T12:02:09.000+05:30
diff --git a/1 Leetcode Easy Problems/Leetcode 278 First Bad Version.java b/1 Leetcode Easy Problems/Leetcode 278 First Bad Version.java
@@ -47,16 +47,16 @@ public static void main(String[] args) {
     }
 
     public int firstBadVersion(int n) {
-        int beg = 1, end = n;
+        long beg = 1, end = n;
         while (beg <= end) {
-            int mid = (beg + end) / 2;
+            int mid = (int) ((beg + end) / 2);
             if (isBadVersion(mid)) {
                 end = mid - 1;
             } else {
                 beg = mid + 1;
             }
         }
-        return end + 1;
+        return (int) end + 1;
     }
 
     public int firstBadVersionLinearSearch(int n) {
diff --git a/1 Leetcode Easy Problems/Leetcode 374 Guess Number Higher or Lower.java b/1 Leetcode Easy Problems/Leetcode 374 Guess Number Higher or Lower.java
@@ -46,16 +46,16 @@ public static void main(String[] args) {
     }
 
     public int guessNumber(int n) {
-        int beg = 1, end = n;
+        long beg = 1, end = n;
         while (beg <= end) {
-            int mid = (beg + end) / 2;
-            int res = guess(mid);
-            if (res == 0)
-                return mid;
-            if (res == -1)
-                end = mid - 1;
-            else
-                beg = mid + 1;
+          int mid = (int) ((beg + end) / 2);
+          int res = guess(mid);
+          if (res == 0)
+            return mid;
+          if (res == -1)
+            end = mid - 1;
+          else
+            beg = mid + 1;
         }
         return -1;
     }
diff --git a/1 Leetcode Easy Problems/Leetcode 441 Arranging Coins.java b/1 Leetcode Easy Problems/Leetcode 441 Arranging Coins.java
@@ -31,19 +31,19 @@ public static void main(String[] args) {
     }
 
     private int arrangeCoins(int n) {
-        int begin = 0;
-        int end = n;
+        long begin = 0;
+        long end = (int) Math.sqrt(2 * (long) n); // Adjust the initial end value
         while (begin <= end) {
-            int mid = (begin + end) / 2;
-            int coinsUsed = (mid * (mid + 1)) / 2;
-            if (coinsUsed == n)
-                return mid;
-            if (coinsUsed < n) {
-                begin = mid + 1;
-            } else {
-                end = mid - 1;
-            }
+          long mid = (begin + end) / 2;
+          long coinsUsed = (mid * (mid + 1)) / 2;
+          if (coinsUsed == n)
+            return (int) mid;
+          if (coinsUsed < n) {
+            begin = mid + 1;
+          } else {
+            end = mid - 1;
+          }
         }
-        return end;
+        return (int) end;
     }
 }
diff --git a/2 Leetcode Medium Problems/Leetcode 33 Search in Rotated Sorted Array.java b/2 Leetcode Medium Problems/Leetcode 33 Search in Rotated Sorted Array.java
@@ -1,76 +1,34 @@
-
-/**
- * There is an integer array nums sorted in ascending
- * order (with distinct values).
- *
- * Prior to being passed to your function, nums is
- * possibly rotated at an unknown pivot index
- * k (1 <= k < nums.length) such that the resulting
- * array is [nums[k], nums[k+1], ..., nums[n-1],
- * nums[0], nums[1], ..., nums[k-1]] (0-indexed).
- * For example, [0,1,2,4,5,6,7] might be rotated
- * at pivot index 3 and become [4,5,6,7,0,1,2].
- *
- * Given the array nums after the possible rotation
- * and an integer target, return the index of
- * target if it is in nums, or -1 if it is not in
- * nums.
- *
- * You must write an algorithm with O(log n) runtime
- * complexity.
- *
- *
- * Example 1: 0,1,2,3,4,5,6
- * Input: nums = [4,5,6,7,0,1,2], target = 0
- * Output: 4
- *
- * Example 2:
- * Input: nums = [4,5,6,7,0,1,2], target = 3
- * Output: -1
- *
- * Example 3:
- * Input: nums = [1], target = 0
- * Output: -1
- *
- *
- * Constraints:
- * 1 <= nums.length <= 5000
- * -104 <= nums[i] <= 104
- * All values of nums are unique.
- * nums is an ascending array that is possibly rotated.
- * -104 <= target <= 104
- */
-class SearchInRotatedSortedArray {
-    public static void main(String[] args) {
-        SearchInRotatedSortedArray search = new SearchInRotatedSortedArray();
-        int[] nums = new int[] { 4, 5, 6, 7, 0, 1, 2 };
-        System.out.println("Found at:"
-                + search.search(nums, 3));
-    }
-
-    int search(int[] nums, int target) {
+class Solution {
+    public int search(int[] nums, int target) {
         int beg = 0, end = nums.length - 1;
-        while (beg <= end) {
+        
+        // First, find the smallest element's index (pivot index)
+        while (beg < end) {
             int mid = (beg + end) / 2;
-            if (nums[mid] > nums[end])
-                beg = mid + 1;
-            else
-                end = mid - 1;
+            if (nums[mid] > nums[end]) {
+                beg = mid + 1;  // pivot must be to the right of mid
+            } else {
+                end = mid;      // pivot could be at mid, or to the left of mid
+            }
         }
-        int shift = end + 1;
+        // Now, beg == end == pivot index (smallest element index)
+        int pivot = beg;
 
+        // Reset beg and end for standard binary search, adjusted by pivot
         beg = 0;
         end = nums.length - 1;
         while (beg <= end) {
             int mid = (beg + end) / 2;
-            int realMid = (mid + shift) % nums.length;
-            if (nums[realMid] == target)
+            int realMid = (mid + pivot) % nums.length;  // Adjust mid to account for rotation
+
+            if (nums[realMid] == target) {
                 return realMid;
-            else if (nums[realMid] < target)
+            } else if (nums[realMid] < target) {
                 beg = mid + 1;
-            else
+            } else {
                 end = mid - 1;
+            }
         }
-        return -1;
+        return -1;        
     }
 }

Original file line number	Diff line number	Diff line change
`@@ -47,16 +47,16 @@ public static void main(String[] args) {`
`47`	`47`	`}`
`48`	`48`
`49`	`49`	`public int firstBadVersion(int n) {`
`50`		`- int beg = 1, end = n;`
	`50`	`+ long beg = 1, end = n;`
`51`	`51`	`while (beg <= end) {`
`52`		`- int mid = (beg + end) / 2;`
	`52`	`+ int mid = (int) ((beg + end) / 2);`
`53`	`53`	`if (isBadVersion(mid)) {`
`54`	`54`	`end = mid - 1;`
`55`	`55`	`} else {`
`56`	`56`	`beg = mid + 1;`
`57`	`57`	`}`
`58`	`58`	`}`
`59`		`- return end + 1;`
	`59`	`+ return (int) end + 1;`
`60`	`60`	`}`
`61`	`61`
`62`	`62`	`public int firstBadVersionLinearSearch(int n) {`