Last active
August 15, 2021 05:52
-
-
Save vaquarkhan/35b047e441e23a25bdcd9f64ef0b3138 to your computer and use it in GitHub Desktop.
Algorithm-Java-programming- Arrays
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
https://www.interviewbit.com/problems/add-one-to-number/ | |
import java.util.ArrayList; | |
import java.util.Arrays; | |
public class AddOneToNumber { | |
public static void main(String[] args) { | |
System.out.println(Arrays.toString(addOne(new int[] {}))); | |
System.out.println(Arrays.toString(addOne(new int[] { 1 }))); | |
System.out.println(Arrays.toString(addOne(new int[] { 9 }))); | |
System.out.println(Arrays.toString(addOne(new int[] { 3, 9, 9 }))); | |
System.out.println(Arrays.toString(addOne(new int[] { 3, 9, 9, 9 }))); | |
System.out.println(Arrays.toString(addOne(new int[] { 9, 9, 9, 9 }))); | |
System.out.println(Arrays.toString(addOne(new int[] { 9, 9, 9, 8 }))); | |
// | |
// | |
ArrayList<Integer> A = new ArrayList<Integer>(); | |
A.add(9); | |
A.add(9); | |
A.add(9); | |
A.add(8); | |
System.out.println("--------------------------"); | |
System.out.println(Arrays.toString(addOne1(A))); | |
} | |
public static int plusOne(ArrayList<Integer> A) { | |
int sum = 0; | |
String str = ""; | |
for (int i = 0; i <= A.size(); i++) { | |
str += A.get(i); | |
} | |
sum = Integer.parseInt(str) + 1; | |
return sum; | |
} | |
public static final int[] addOne(int[] digits) { | |
int carry = 1; | |
int[] result = new int[digits.length]; | |
for (int i = digits.length - 1; i >= 0; i--) { | |
int val = digits[i] + carry; | |
result[i] = val % 10; | |
carry = val / 10; | |
} | |
if (carry == 1) { | |
result = new int[digits.length + 1]; | |
result[0] = 1; | |
} | |
return result; | |
} | |
public static final int[] addOne1(ArrayList<Integer> A) { | |
int carry = 1; | |
int[] result = new int[A.size()]; | |
for (int i = A.size()-1; i >= 0; i--) { | |
int val = A.get(i) + carry; | |
result[i] = val % 10; | |
carry = val / 10; | |
} | |
if (carry == 1) { | |
result = new int[A.size()]; | |
result[0] = 1; | |
} | |
return result; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
My learning |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
https://www.interviewbit.com/problems/balance-array/ | |
package com.array; | |
import java.util.ArrayList; | |
import java.util.Arrays; | |
import java.util.List; | |
/** | |
* Given an integer array A of size N. You need to count the number of special | |
* elements in the given array. | |
* | |
* A element is special if removal of that element make the array balanced. | |
* | |
* Array will be balanced if sum of even index element equal to sum of odd index | |
* element. | |
* | |
* | |
* @author vkhan | |
* | |
*/ | |
public class BalanceArrayonRemoval { | |
public static void main(String args[]) { | |
// [2, 1, 6, 4] | |
// [5, 5, 2, 5, 8] | |
Integer arr1[] = { 2, 1, 6, 4 }; | |
Integer arr2[] = { 5, 5, 2, 5, 8 }; | |
System.out.println(solve(Arrays.asList(arr1))); | |
System.out.println(solve(Arrays.asList(arr2))); | |
} | |
//Editorial | |
static int solve(List<Integer> A) { | |
if (A.size() == 1) | |
return 1; | |
int[] cumsum = new int[A.size()]; | |
int count = 0, evensum = 0, oddsum = 0, evenSumTot = 0, oddSumTot = 0; | |
cumsum[0] = A.get(0); | |
cumsum[1] = A.get(1); | |
// cumsum[0, 2, 4, ...] are even sum and cumsum[1, 3, 5, ...] are odd sum | |
for (int i = 2; i < A.size(); ++i) | |
cumsum[i] = cumsum[i - 2] + A.get(i); | |
// depending on size of input array the total odd sum and the total odd sum | |
// will be in different position of cumsum array | |
// eg n=5 then osumtot = (1,3) ie cumsum[n-2] ; esumtot = (0,2,4)()ie | |
// cumsum[n-1] | |
if (A.size() % 2 == 1) { | |
oddSumTot = cumsum[A.size() - 2]; | |
evenSumTot = cumsum[A.size() - 1]; | |
} else // (A.size()%2==0) | |
{ | |
oddSumTot = cumsum[A.size() - 1]; | |
evenSumTot = cumsum[A.size() - 2]; | |
} | |
int pre; | |
for (int i = 0; i < A.size(); ++i) { | |
if (i == 0) | |
pre = 0; // when considering removing first index we set previous sum to | |
// be zero | |
else | |
pre = cumsum[i - 1]; | |
// iterate over each positon to find esum and osum when that index is removed | |
if (i % 2 == 1)// if i is 0dd | |
{ | |
evensum = pre + (oddSumTot - cumsum[i]); | |
oddsum = cumsum[i] + (evenSumTot - pre) - A.get(i); | |
} else// i is even | |
{ | |
evensum = cumsum[i] + (oddSumTot - pre) - A.get(i); | |
oddsum = pre + (evenSumTot - cumsum[i]); | |
} | |
if (evensum == oddsum) | |
count++; | |
} | |
return count; | |
} | |
//Fastest | |
public int solve1(ArrayList<Integer> a) { | |
if (a == null || a.size() == 2) { | |
return 0; | |
} | |
if (a.size() == 1) { | |
return 1; | |
} | |
int totalEven = 0; | |
int totalOdd = 0; | |
boolean even = true; | |
for (int i = 0; i < a.size(); i++) { | |
if (even) { | |
totalEven += a.get(i); | |
} else { | |
totalOdd += a.get(i); | |
} | |
even = !even; | |
} | |
int lEven = 0; | |
int rEven = 0; | |
int lOdd = 0; | |
int rOdd = 0; | |
int count = 0; | |
even = true; | |
for (int i = 0; i < a.size(); i++) { | |
if (even) { | |
rEven = totalEven - lEven - a.get(i); | |
rOdd = totalOdd - lOdd; | |
if ((lEven + rOdd) == (lOdd + rEven)) { | |
count++; | |
} | |
lEven += a.get(i); | |
} else { | |
rEven = totalEven - lEven; | |
rOdd = totalOdd - lOdd - a.get(i); | |
if ((lEven + rOdd) == (lOdd + rEven)) { | |
count++; | |
} | |
lOdd += a.get(i); | |
} | |
even = !even; | |
} | |
return count; | |
} | |
// light weight | |
public int solve3(ArrayList<Integer> A) { | |
int n = A.size(); | |
long[][] dp = new long[n + 1][2]; | |
for (int i = n - 1; i >= 0; i--) { | |
dp[i][1] = dp[i + 1][1]; | |
dp[i][0] = dp[i + 1][0]; | |
if (i % 2 == 1) { | |
dp[i][0] += A.get(i); | |
} else { | |
dp[i][1] += A.get(i); | |
} | |
} | |
int cnt = 0; | |
long odd = 0; | |
long even = 0; | |
for (int i = 0; i < A.size(); i++) { | |
long nextOdd = 0; | |
long nextEven = 0; | |
if (i % 2 == 1) { | |
nextOdd = odd + dp[i][1]; | |
nextEven = even + dp[i][0] - A.get(i); | |
} else { | |
nextOdd = odd + dp[i][1] - A.get(i); | |
nextEven = even + dp[i][0]; | |
} | |
if (nextOdd == nextEven) { | |
cnt++; | |
} | |
if (i % 2 == 1) { | |
odd += A.get(i); | |
} else { | |
even += A.get(i); | |
} | |
} | |
return cnt; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
https://www.hackerrank.com/challenges/big-sorting/problem | |
static String[] bigSorting(String[] unsorted) { | |
if (null == unsorted) | |
return unsorted; | |
// | |
Arrays.sort(unsorted, new Comparator<String>() { | |
@Override | |
public int compare(String o1, String o2) { | |
// TODO Auto-generated method stub | |
return compareStrings(o1, o2);// Integer.valueOf(o1).compareTo(Integer.valueOf(o2)); | |
} | |
}); | |
for (String s : unsorted) | |
System.out.println("number1=" + s); | |
return unsorted; | |
} | |
private static int compareStrings(String s1, String s2) { | |
// | |
if (s1.length() < s2.length()) { | |
return -1; | |
} else if (s1.length() > s2.length()) { | |
return 1; | |
} | |
for (int i = 0; i < s1.length(); i++) { | |
if ((int) s1.charAt(i) < (int) s2.charAt(i)) | |
return -1; | |
if ((int) s1.charAt(i) > (int) s2.charAt(i)) | |
return 1; | |
} | |
return 0; | |
} | |
//Java 8 | |
Arrays.sort(unsorted, (left, right) -> { | |
if (left.length() != right.length()) { | |
return left.length() - right.length(); | |
} else { | |
return left.compareTo(right); | |
} | |
}); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.ArrayList; | |
import java.util.LinkedList; | |
import java.util.List; | |
import java.util.Queue; | |
public class BinarayreeRightSideView { | |
public static void main(String[] args) { | |
} | |
public List<Integer> rightSideView(TreeNode root) { | |
List<Integer> res = new ArrayList<Integer>(); | |
if (root == null) { | |
return res; | |
} | |
// | |
Queue<TreeNode> queue = new LinkedList<TreeNode>(); | |
queue.offer(root); | |
// queue.remove(root); | |
// | |
while (!queue.isEmpty()) { | |
TreeNode cur = queue.peek(); | |
int curSize = queue.size(); | |
for (int i = 0; i < curSize; i++) { | |
cur = queue.poll(); | |
if (cur.left != null) { | |
queue.offer(cur.left); | |
// queue.add(cur.left); | |
} | |
if (cur.right != null) { | |
queue.offer(cur.right); | |
// queue.add(cur.right); | |
} | |
} | |
res.add(cur.val); | |
} | |
return res; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
- https://leetcode.com/problems/buddy-strings/submissions/ | |
import java.util.ArrayList; | |
import java.util.HashSet; | |
import java.util.List; | |
import java.util.Set; | |
public class BuddyString { | |
public static void main(String[] args) { | |
String A = "aa"; | |
String B = "aa"; | |
System.out.println(buddyStrings(A, B)); | |
} | |
public static boolean buddyStrings(String A, String B) { | |
if (A.length() != B.length()) | |
return false; | |
if (A.equals(B)) { | |
Set<Character> set = new HashSet(); | |
for (char ch : A.toCharArray()) { | |
set.add(ch); | |
} | |
//if B size less means duplicate char | |
//example in case A=aa b=aa its save a and return true | |
//in case A=ab B=ab then store ab and condition return false | |
return set.size() < A.length(); | |
} | |
List<Integer> diff = new ArrayList(); | |
//if diff size is more then 2 means not swap 1 char | |
for (int i = 0; i < A.length(); i++) { | |
if (A.charAt(i) != B.charAt(i)) { | |
diff.add(i); | |
if (diff.size() > 2) { | |
return false; | |
} | |
} | |
} | |
return diff.size() == 2 && A.charAt(diff.get(0)) == B.charAt(diff.get(1)) && A.charAt(diff.get(1)) == B.charAt(diff.get(0)); | |
} | |
public static boolean buddyStrings1(String A, String B) { | |
// | |
if (null == A || A.isEmpty()) | |
return false; | |
// | |
if (null == B || B.isEmpty()) | |
return false; | |
// | |
if (A.length() != B.length()) { | |
return false; | |
} else { | |
char arr1[] = A.toCharArray(); | |
char arr2[] = B.toCharArray(); | |
for (int i = 0; i < arr1.length; i++) { | |
if (A.charAt(i) == B.charAt(i)) { | |
} | |
} | |
} | |
return false; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//https://www.geeksforgeeks.org/count-pairs-difference-equal-k/ | |
public class DiffrenceK { | |
static int countPairsWithDiffK(int arr[], int k) { | |
int count = 0; | |
// Pick all elements one by one | |
for (int i = 0; i < arr.length; i++) { | |
// See if there is a pair of this picked element | |
for (int j = i + 1; j < arr.length; j++) | |
if (arr[i] - arr[j] == k || arr[j] - arr[i] == k) { | |
count++; | |
} | |
} | |
return count; | |
} | |
// Driver code | |
public static void main(String args[]) { | |
int arr[] = { 1, 5, 3, 4, 2 }; | |
int k = 3; | |
System.out.println("Count of pairs with given diff is " + countPairsWithDiffK(arr, k)); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
- https://leetcode.com/problems/count-the-number-of-consistent-strings/ | |
class Solution { | |
public int countConsistentStrings(String allowed, String[] words) { | |
Map<Character, Integer> map = new HashMap(); | |
//Add all allowed char to map and count | |
//since key overrite if get dupicate so no count needed | |
for (char ch : allowed.toCharArray()) { | |
map.put(ch, 1); | |
} | |
// | |
int count = 0; | |
for (String str : words) { | |
// Add no matter what | |
count++; | |
// | |
for (char ch : str.toCharArray()) { | |
if (map.get(ch) == null) { | |
// Only if we find no match will we decrement and break loop | |
count--; | |
break; | |
} | |
} | |
} | |
return count; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer. | |
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc. | |
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4]. | |
Examples: | |
s = "3[a]2[bc]", return "aaabcbc". | |
s = "3[a2[c]]", return "accaccacc". | |
s = "2[abc]3[cd]ef", return "abcabccdcdcdef". | |
import java.util.Stack; | |
public class StringDecoding { | |
/** | |
* s = "3[a]2[bc]", return "aaabcbc". | |
* s = "3[a2[c]]", return "accaccacc". | |
* s = "2[abc]3[cd]ef", return "abcabccdcdcdef". | |
* | |
* @param args | |
*/ | |
public static void main(String[] args) { | |
// TODO Auto-generated method stub | |
String str = "3[a]2[bc]"; | |
System.out.println("result=" + decodeString1(str)); | |
} | |
public static String decodeString1(String s) { | |
if (s.length() == 0 || s == null) { | |
return s; | |
} | |
Stack<String> strStack = new Stack<String>(); | |
Stack<Integer> numStack = new Stack<Integer>(); | |
StringBuilder res = new StringBuilder(); | |
int index = 0; | |
// | |
while (index < s.length()) { | |
if (Character.isDigit(s.charAt(index))) { | |
int num = 0; | |
// if 32[a] will come then | |
// num = 0 so 0*10+(3) | |
// num=3 | |
// now come 2 so 3*10+2 =32 | |
// if 3 will come | |
while (Character.isDigit(s.charAt(index))) { | |
num = num * 10 + (s.charAt(index) - '0'); | |
index++; | |
} | |
numStack.push(num); | |
} else if (s.charAt(index) == '[') { | |
strStack.push(res.toString()); | |
res = new StringBuilder(""); | |
index++; | |
} else if (s.charAt(index) == ']') { | |
StringBuilder temp = new StringBuilder(strStack.pop()); | |
int repeatTimes = numStack.pop(); | |
for (int i = 0; i < repeatTimes; i++) { | |
temp.append(res); | |
} | |
res = temp; | |
index++; | |
} else { | |
res.append(s.charAt(index++)); | |
} | |
} | |
return res.toString(); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//https://www.interviewbit.com/problems/find-duplicate-in-array/ | |
public ArrayList<Integer> repeatedNumber(final List<Integer> a) { | |
Int [] arr= {247, 240, 303, 9, 304, 105, 44, 204, 291, 26, 242, 2, 358, 264, 176, 289, 196, 329, | |
189, 102, 45, 111, 115, 339, 74, 200, 34, 201, 215, 173, 107, 141, 71, 125, 6, 241, 275, 88, | |
91, 58, 171, 346, 219, 238, 246, 10, 118, 163, 287, 179, 123, 348, 283, 313, 226, 324, 203, | |
323, 28, 251, 69, 311, 330, 316, 320, 312, 50, 157, 342, 12, 253, 180, 112, 90, 16, 288, 213, 273, | |
57, 243, 42, 168, 55, 144, 131, 38, 317, 194, 355, 254, 202, 351, 62, 80, 134, 321, 31, 127, 232, 67, | |
22, 124, 271, 231, 162, 172, 52, 228, 87, 174, 307, 36, 148, 302, 198, 24, 338, 276, 327, 150, 110, 188, | |
309, 354, 190, 265, 3, 108, 218, 164, 145, 285, 99, 60, 286, 103, 119, 29, 75, 212, 290, 301, 151, 17, | |
147, 94, 138, 272, 279, 222, 315, 116, 262, 1, 334, 41, 54, 208, 139, 332, 89, 18, 233, 268, 7, 214, | |
20, 46, 326, 298, 101, 47, 236, 216, 359, 161, 350, 5, 49, 122, 345, 269, 73, 76, 221, 280, 322, | |
149, 318, 135, 234, 82, 120, 335, 98, 274, 182, 129, 106, 248, 64, 121, 258, 113, 349, 167, 192, 356, | |
51, 166, 77, 297, 39, 305, 260, 14, 63, 165, 85, 224, 19, 27, 177, 344, 33, 259, 292, 100, 43, 314, 170, | |
97, 4, 78, 310, 61, 328, 199, 255, 159, 185, 261, 229, 11, 295, 353, 186, 325, 79, 142, 223, 211, 152, 266, | |
48, 347, 21, 169, 65, 140, 83, 156, 340, 56, 220, 130, 117, 143, 277, 235, 59, 205, 153, 352, 300, 114, 84, | |
183, 333, 230, 197, 336, 244, 195, 37, 23, 206, 86, 15, 187, 181, 308, 109, 293, 128, 66, 270, 209, 158, 32, | |
25, 227, 191, 35, 40, 13, 175, 146, 299, 207, 217, 281, 30, 357, 184, 133, 245, 284, 343, 53, 210, 306, 136, | |
132, 239, 155, 73, 193, 278, 257, 126, 331, 294, 250, 252, 263, 92, 267, 282, 72, 95, 337, 154, 319, 341, 70, | |
81, 68, 160, 8, 249, 96, 104, 137, 256, 93, 178, 296, 225, 237}; | |
Arrays.asList(arr); | |
ArrayList<Integer> res = new ArrayList<Integer>(); | |
int n = a.size(); | |
long sumOfNum = (((long) n) * ((long) n + 1)) / 2; | |
long sumOfSq = (((long) n) * ((long) n + 1) * ((long) 2*n + 1)) / 6; | |
for (int i=0; i < n; i++) { | |
sumOfNum -= (long) a.get(i); | |
} | |
for (int i=0; i < n; i++) { | |
sumOfSq -= (long) a.get(i) * (long) a.get(i); | |
} | |
long sumNum = sumOfSq/sumOfNum; | |
int missing = (int) (sumNum + sumOfNum)/2; | |
int repeated = (int) (sumNum - missing); | |
res.add(repeated); | |
res.add(missing); | |
return res; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com; | |
import java.util.HashMap; | |
import java.util.Map; | |
public class DuplicateWordsString { | |
public static void main(String[] args) { | |
String str = "Hi i am vaquar khan and khan is good people"; | |
dubplicateFInd(str); | |
} | |
private static void dubplicateFInd(String str) { | |
String[] str1 = str.split(" "); | |
Map<String, Integer> map = new HashMap(); | |
// for (int i = 0; i < str1.length; i++) { | |
for (String sr : str1) { | |
// | |
if (!map.containsKey(sr)) { | |
map.put(sr, 1); | |
} else { | |
map.put(sr, map.get(sr) + 1); | |
} | |
} | |
for (Map.Entry<String, Integer> entry : map.entrySet()) { | |
System.out.println(entry.getKey() + ":" + entry.getValue()); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array. | |
Example 1 | |
Input: [3,0,1] | |
Output: 2 | |
Example 2 | |
Input: [9,6,4,2,3,5,7,0,1] | |
Output: 8 | |
Note: | |
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity? | |
*/ | |
/** | |
* Approach 1: HashSet | |
* Using a HashSet to get constant time containment queries and overall linear runtime. | |
* Algorithm | |
* We traverse the array nums and store the elements in the set. | |
* Then we iterator the set, we can easily figure out which number is missing. | |
* | |
* Complexity Analysis | |
* Time complexity : O(n) | |
* Because the set allows for O(1) containment queries, the main loop runs in O(n) time. | |
* Creating num_set costs O(n) time, as each set insertion runs in amortized O(1) time, | |
* so the overall runtime is O(n+n) = O(n). | |
* Space complexity : O(n) | |
* nums contains n-1 distinct elements, so it costs O(n) space to store a set containing all of them. | |
*/ | |
class Solution { | |
public int missingNumber(int[] nums) { | |
Set<Integer> numSet = new HashSet<Integer>(); | |
// store the elements in nums | |
for (int num : nums) { | |
numSet.add(num); | |
} | |
int expectedNumCount = nums.length + 1; | |
// iterator the set to find the missing number | |
for (int number = 0; number < expectedNumCount; number++) { | |
if (!numSet.contains(number)) { | |
return number; | |
} | |
} | |
return -1; | |
} | |
} | |
/** | |
* Approach 2: Bit Manipulation | |
* Intuition | |
* We can harness the fact that XOR is its own inverse to find the missing element in linear time. | |
* Algorithm | |
* Because we know that nums contains n numbers and that | |
* it is missing exactly one number on the range [0..n−1], | |
* we know that n definitely replaces the missing number in nums. | |
* Therefore, if we initialize an integer to n and XOR it with every index and value, | |
* we will be left with the missing number. | |
* | |
* Consider the following example | |
* (the values have been sorted for intuitive convenience, but need not be): | |
* Index 0 1 2 3 | |
* Value 0 1 3 4 | |
* missing = 4^(0^0)^(1^1)^(2^3)^(3^4) | |
* = (4^4)^(0^0)^(1^1)^(3^3)^2 | |
* =0^0^0^0^2 | |
* =2 | |
* | |
* Complexity Analysis | |
* Time complexity : O(n) | |
* Assuming that XOR is a constant-time operation, | |
* this algorithm does constant work on n iterations, so the runtime is overall linear. | |
* Space complexity : O(1) | |
* This algorithm allocates only constant additional space. | |
*/ | |
class Solution { | |
public int missingNumber(int[] nums) { | |
int missing = nums.length; | |
for (int i = 0; i < nums.length; i++) { | |
missing ^= i ^ nums[i]; | |
} | |
return missing; | |
} | |
} | |
/** | |
* Approach 3: Gauss' Formula | |
* Intuition | |
* One of the most well-known stories in mathematics is of a young Gauss, | |
* forced to find the sum of the first 100 natural numbers. | |
* Rather than add the numbers by hand, | |
* he deduced a closed-form expression for the sum. You can see the formula below: | |
* ∑ni=n(n+1)/2 | |
* https://brilliant.org/wiki/sum-of-n-n2-or-n3/ | |
* | |
* Algorithm | |
* We can compute the sum of nums in linear time, | |
* and by Gauss' formula, we can compute the sum of the first n natural numbers in constant time. | |
* Therefore, the number that is missing is simply the result of Gauss' formula minus the sum of nums, | |
* as nums consists of the first n natural numbers minus some number. | |
* | |
* Complexity Analysis | |
* Time complexity : O(n) | |
* Although Gauss' formula can be computed in O(1) time, summing nums costs us O(n) time, | |
* so the algorithm is overall linear. | |
* Because we have no information about which number is missing, | |
* an adversary could always design an input for which any algorithm | |
* that examines fewer than n numbers fails. | |
* Therefore, this solution is asymptotically optimal. | |
* Space complexity : O(1) | |
* This approach only pushes a few integers around, so it has constant memory usage. | |
*/ | |
class Solution { | |
public int missingNumber(int[] nums) { | |
int expectedSum = nums.length * (nums.length + 1) / 2; | |
int actualSum = 0; | |
for (int num : nums) { | |
actualSum += num; | |
} | |
return expectedSum - actualSum; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.array; | |
import java.util.LinkedHashMap; | |
import java.util.Map; | |
public class FirstNonRepeatingCharacterString { | |
; | |
// Driver method | |
public static void main(String[] args) { | |
String str = "geeksforgeeks"; | |
// | |
char index = firstNonRepeating(str); | |
System.out.println(index); | |
//System.out.println(index == -1 ? "Either all characters are repeating or string " + "is empty" | |
// : "First non-repeating character is " + str.charAt(index)); | |
} | |
/* | |
* The method returns index of first non-repeating character in a string. If all | |
* characters are repeating then returns -1 | |
*/ | |
static char firstNonRepeating(String str) { | |
char arr[] = str.toCharArray(); | |
// | |
int count=0; | |
Map<Character,Integer> map = new LinkedHashMap(); | |
char val=' '; | |
// | |
for (int i = 0; i < str.length(); i++) { | |
if(!map.containsKey(arr[i])) { | |
map.put(arr[i], 1); | |
}else { | |
map.put(arr[i],map.get(arr[i])+1); | |
} | |
} | |
for (Map.Entry<Character, Integer> entry : map.entrySet()) { | |
if(entry.getValue()==1) { | |
System.out.println(entry.getKey() + ":" + entry.getValue()); | |
val=entry.getKey(); | |
break; | |
} | |
} | |
return val; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Arrays; | |
import java.util.Comparator; | |
Given a list of non negative integers, arrange them such that they form the largest number. | |
For example: | |
Given [3, 30, 34, 5, 9], the largest formed number is 9534330. | |
Note: The result may be very large, so you need to return a string instead of an integer. | |
public class StringLargestNumber { | |
public static void main(String[] args) { | |
final int[] A = { 3, 30, 34, 5, 9 };// 9534330//3,5,9,30,34 | |
System.out.println(largestNumber(A)); | |
} | |
public static String largestNumber(final int[] A) { | |
String arr[] = new String[A.length]; | |
// | |
for (int i = 0; i <= A.length - 1; i++) { | |
arr[i] = String.valueOf(A[i]); | |
} | |
// | |
Arrays.sort(arr, new Comparator<String>() { | |
public int compare(String a, String b) { | |
return (b + a).compareTo(a + b); | |
} | |
}); | |
StringBuilder sb = new StringBuilder(); | |
for (String s : arr) { | |
sb.append(s); | |
} | |
while (sb.charAt(0) == '0' && sb.length() > 1) { | |
sb.deleteCharAt(0); | |
} | |
return sb.toString(); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//https://www.interviewbit.com/problems/pick-from-both-sides/ | |
package com.array; | |
import java.util.Arrays; | |
import java.util.List; | |
public class PickFromBothSides { | |
public static void main(String[] args) { | |
Integer[] arr = { 5, -2, 3, 1, 2 }; | |
System.out.println(solve(Arrays.asList(arr), 3)); | |
} | |
public static int solve(List<Integer> A, int B) { | |
int n = A.size(); | |
int result = 0; | |
for (int i = 0; i < B; i++) { | |
result += A.get(i); | |
} | |
int sum = result; | |
for (int i = 0; i < B; i++) { | |
sum -= A.get(B - 1 - i); | |
sum += A.get(n - 1 - i); | |
result = Math.max(result, sum); | |
} | |
return result; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
- https://leetcode.com/problems/design-parking-system/ | |
/** | |
* How Many Numbers Are Smaller Than the Current Number. | |
* See {@link <a href ="https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/">https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/</a>} | |
*/ | |
final class HowManySmallerNumbers { | |
public static void main (String args[] ) { | |
int nums [] = {8,1,2,2,3}; | |
smallerNumbersThanCurrent(nums) ; | |
} | |
static int[] smallerNumbersThanCurrent(final int[] nums) { | |
int max = 0; | |
//Step 1: Find max no in array | |
for (int i = 0; i < nums.length; i++) { | |
max = Math.max(max, nums[i]); | |
} | |
//Step 2 create new array and fill table count | |
/** | |
* filling array | |
* 8,1,2,2,3 | |
* | |
* 0 1 2 3 4 5 6 7 8 9 | |
* ----------------------------------------- | |
* | 0 |1 | 2 | 1 | 0 |0 |0 |0 |1 |0 | | |
* ----------------------------------------- | |
* | |
* <----------------------------------- | |
*/ | |
final int[] sum = new int[max + 1]; | |
for (int i = 0; i < nums.length; i++) { | |
sum[nums[i]]++; | |
} | |
//Step 3: | |
for (int i = 1; i < sum.length; i++) { | |
sum[i] += sum[i - 1]; | |
} | |
//Step 4: | |
for (int i = 0; i < nums.length; i++) { | |
if (nums[i] != 0) { | |
nums[i] = sum[nums[i] - 1]; | |
} | |
} | |
return nums; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
https://www.lintcode.com/problem/920/ | |
public static boolean canAttendMeetings(List<Interval> intervals) { | |
int [] startInv=new int[intervals.size()]; | |
int [] endInv=new int[intervals.size()]; | |
for(int i=0;i<intervals.size();i++) { | |
//set value in two arra | |
startInv[i]= intervals.get(i).start; | |
endInv[i]= intervals.get(i).end; | |
} | |
// Sort Array | |
Arrays.sort(startInv); | |
Arrays.sort(endInv); | |
//Compare | |
for(int i=0;i<startInv.length-1;i++) { | |
if(startInv[i+1] <endInv[i]) { | |
return false; | |
} | |
} | |
return true; | |
} | |
static class Interval { | |
int start, end; | |
Interval(int start, int end) { | |
this.start = start; | |
this.end = end; | |
} | |
public int getStart() { | |
return start; | |
} | |
public void setStart(int start) { | |
this.start = start; | |
} | |
public int getEnd() { | |
return end; | |
} | |
public void setEnd(int end) { | |
this.end = end; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
https://leetcode.com/problems/valid-parentheses/submissions/ | |
import java.util.ArrayDeque; | |
import java.util.Deque; | |
public class ValidParentheses2 { | |
public static void main(String[] args) { | |
// TODO Auto-generated method stub | |
System.out.println(isValidParentheses("((")); | |
} | |
public static boolean isValidParentheses(String s) { | |
Deque<Character> stack = new ArrayDeque(); | |
for(int i =0;i<s.length();i++) { | |
//push left parenthsis into stack | |
if(s.charAt(i)=='('|| s.charAt(i)=='{' || s.charAt(i)=='[') { | |
stack.push(s.charAt(i)); | |
}else { | |
if(!stack.isEmpty()) { | |
char c= stack.pop(); | |
if( | |
(c=='(' && s.charAt(i)==')') || | |
(c=='[' && s.charAt(i)==']') || | |
(c =='{' && s.charAt(i)=='}') | |
){ | |
return false; | |
} | |
} | |
} | |
} | |
return true; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.solution.sorting; | |
import java.util.HashSet; | |
import java.util.Set; | |
public class SumOfTwo2 { | |
/** | |
* | |
* A=[0,0,-5,30212] B=[-10,40,-3,9] v=-8 | |
* | |
* -5 + -3 = -8 subOfTwo(a,b,v)= true | |
* | |
* @param args | |
*/ | |
public static void main(String[] args) { | |
int a[] = { 0, 0, -5, 30212 }; | |
int b[] = { -10, 40, -3, 9 }; | |
int v = -8; | |
twoSum(a, b, v); | |
twoSum1(a, b, v); | |
} | |
// O(n*n) | |
public static boolean twoSum(int[] a, int[] b, int v) { | |
for (int i = 0; i < a.length; i++) { | |
for (int j = 0; j < b.length; j++) { | |
if ((a[i] + b[i]) == v) { | |
System.out.println(a[i] + b[i]); | |
return true; | |
} | |
} | |
} | |
return false; | |
} | |
// O(n) | |
public static boolean twoSum1(int[] a, int[] b, int v) { | |
Set<Integer> set = new HashSet(); | |
for (int i = 0; i < a.length; i++) { | |
set.add(v - a[i]); | |
} | |
for (int j = 0; j < b.length; j++) { | |
if (set.contains(b[j])) { | |
System.out.println(b[j]); | |
return true; | |
} | |
} | |
return false; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//https://leetcode.com/problems/group-anagrams/submissions/ | |
package com; | |
import java.util.ArrayList; | |
import java.util.Arrays; | |
import java.util.HashMap; | |
import java.util.List; | |
import java.util.Map; | |
/** | |
* Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: | |
* [["bat"],["nat","tan"],["ate","eat","tea"]] | |
* | |
* Example 2: | |
* | |
* Input: strs = [""] Output: [[""]] | |
* | |
* Example 3: | |
* | |
* Input: strs = ["a"] Output: [["a"]] | |
* | |
* | |
* | |
*/ | |
public class Anagrams1 { | |
public static void main(String[] args) { | |
String[] strs = { "eat", "tea", "tan", "ate", "nat", "bat" }; | |
List<List<String>> list = groupAnagrams(strs); | |
for (List li : list) { | |
System.out.println(li); | |
} | |
} | |
public static List<List<String>> groupAnagrams(String[] strs) { | |
Map<String, List<String>> map = new HashMap<>(); | |
// | |
for (String word : strs) { | |
char[] c = word.toCharArray(); | |
// | |
Arrays.sort(c); | |
//System.out.println("=C="+c.toString()); | |
String hash = new String(c); | |
//System.out.println("=contain=hash="+hash); | |
// | |
if (map.containsKey(hash)) { | |
map.get(hash).add(word); | |
} else { | |
// | |
List<String> list = new ArrayList<>(); | |
list.add(word); | |
map.put(hash, list); | |
} | |
} | |
return new ArrayList<List<String>>(map.values()); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
https://www.interviewbit.com/problems/hotel-bookings-possible/ | |
import java.util.ArrayList; | |
import java.util.Collections; | |
public class HotelBookingsPossibl { | |
public static void main(String[] args) { | |
ArrayList<Integer> arrive = new ArrayList<Integer>(); | |
arrive.add(1); | |
arrive.add(3); | |
arrive.add(5); | |
ArrayList<Integer> depart = new ArrayList<Integer>(); | |
depart.add(2); | |
depart.add(6); | |
depart.add(8); | |
int K = 1; | |
System.out.println(hotel(arrive,depart,K)); | |
} | |
public static boolean hotel(ArrayList<Integer> arrive, ArrayList<Integer> depart, int K) { | |
if (null == arrive || arrive.isEmpty()) | |
return false; | |
if (null == depart || depart.isEmpty()) | |
return false; | |
if (K == 0) | |
return false; | |
// both list sort | |
Collections.sort(arrive); | |
Collections.sort(depart); | |
// | |
int n = arrive.size(); | |
int currBookingCount = 1; | |
int maxBookingCount = 1; | |
int arriveIdx = 1; | |
int departIdx = 0; | |
// | |
while (arriveIdx < n && departIdx < n) { | |
if (arrive.get(arriveIdx) < depart.get(departIdx)) { | |
currBookingCount++; | |
maxBookingCount = Math.max(maxBookingCount, currBookingCount); | |
arriveIdx++; | |
} else { | |
currBookingCount--; | |
departIdx++; | |
} | |
if (maxBookingCount > K) { | |
return false; | |
} | |
} | |
return true; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Solution { | |
public int lengthOfLongestSubstring(String s) { | |
if (s == null || s.length() == 0){ | |
return 0; | |
} | |
int max = 1; | |
int start = 0; | |
int end = 1; | |
HashMap<Character, Integer> map = new HashMap<Character, Integer>(); | |
map.put(s.charAt(0), 0); | |
while (end < s.length()){ | |
char c = s.charAt(end); | |
if (map.containsKey(c) && map.get(c) >= start){ | |
start = map.get(c) + 1; | |
} | |
map.put(c, end); | |
max = Math.max(max, end - start + 1); | |
end++; | |
} | |
return max; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
https://www.interviewbit.com/problems/max-sum-contiguous-subarray/ | |
public int maxSubArray(final List<Integer> A){ | |
int currMax = A.get(0); | |
int tempMax = A.get(0); | |
for(int i=1;i<A.size();i++){ | |
if(A.get(i)>tempMax+A.get(i)){ | |
tempMax=A.get(i); | |
} | |
else{ | |
tempMax+=A.get(i); | |
} | |
if(currMax < tempMax){ | |
currMax=tempMax; | |
} | |
} | |
return currMax; | |
} | |
================ | |
public int maxSubArray(final List<Integer> A){ | |
int currMax = A.get(0); | |
int tempMax = A.get(0); | |
for(int i=1;i<A.size();i++){ | |
if(A.get(i)>tempMax+A.get(i)){ | |
tempMax=A.get(i); | |
} | |
else{ | |
tempMax+=A.get(i); | |
} | |
if(currMax < tempMax){ | |
currMax=tempMax; | |
} | |
} | |
return currMax; | |
} | |
=============== | |
public int maxSubArray(final List<Integer> A) { | |
int maxEndingHere = A.get(0); | |
int maxSoFar = A.get(0); | |
for (int i = 1; i < A.size(); i++) { | |
maxEndingHere = Math.max(A.get(i), A.get(i) + maxEndingHere); | |
maxSoFar = Math.max(maxSoFar, maxEndingHere); | |
} | |
return maxSoFar; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.ArrayList; | |
import java.util.Arrays; | |
import java.util.Collections; | |
import java.util.List; | |
public class MaximumConsecutiveGap { | |
/** | |
* Input : [1, 10, 5] Output : 5 | |
* | |
* @param args | |
*/ | |
public static void main(String[] args) { | |
int arr[] = { 1, 10, 5 }; | |
final List<Integer> A = new ArrayList(); | |
A.add(1); | |
A.add(10); | |
A.add(5); | |
System.out.println(maximumGap(A)); | |
} | |
public static int maximumGap(final List<Integer> A) { | |
if (null == A || A.isEmpty()) | |
return 0; | |
if (A.size() == 2) | |
return 0; | |
// Find maximum and minimum in arr[] | |
Collections.sort(A); | |
// | |
int max = 0; | |
for (int i = 0; i < A.size() - 1; i++) { | |
if (A.get(i + 1) - A.get(i) > max) | |
max = A.get(i + 1) - A.get(i); | |
} | |
return max; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
https://www.interviewbit.com/problems/maximum-absolute-difference/ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public static double findMedianSortedArrays(int[] ar1, int[] ar2) { | |
int[] result = new int[ar1.length + ar2.length]; | |
double medianVal = 0; | |
// | |
mergeArray(result, ar1, ar2); | |
// | |
int median = ar1.length + ar2.length; | |
if (median % 2 == 0) { | |
// | |
medianVal = (double) ((result[(median / 2) - 1] + result[median / 2])) / 2; | |
// | |
System.out.println(medianVal); | |
} else { | |
medianVal = result[median / 2]; | |
System.out.println(medianVal); | |
} | |
return medianVal; | |
} | |
static void mergeArray(int[] result, int[] a, int[] b) { | |
int first = 0; | |
int second = 0; | |
// | |
for (int i = 0; i < a.length + b.length; i++) { | |
if (first < a.length && second < b.length) | |
if (a[first] < b[second]) { | |
result[i] = a[first]; | |
first++; | |
} else { | |
result[i] = b[second]; | |
second++; | |
} | |
else { | |
if (second == b.length && first < a.length) { | |
result[i] = a[first]; | |
first++; | |
} | |
if (first == a.length && second < b.length) { | |
result[i] = b[second]; | |
second++; | |
} | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
https://www.interviewbit.com/problems/min-steps-in-infinite-grid/ | |
import java.util.ArrayList; | |
public class CoverPoints { | |
public static void main(String[] args) { | |
ArrayList<Integer> x = new ArrayList<>(); | |
x.add(0); | |
x.add(1); | |
x.add(1); | |
ArrayList<Integer> y = new ArrayList<>(); | |
y.add(0); | |
y.add(1); | |
y.add(2); | |
System.out.println(coverPoints(x, y)); | |
} | |
public static int coverPoints(ArrayList<Integer> A, ArrayList<Integer> B) { | |
// | |
int count = 0; | |
for (int i = 1; i < A.size(); i++) { | |
// | |
int x = Math.abs(A.get(i) - A.get(i - 1)); | |
int y = Math.abs(B.get(i) - B.get(i - 1)); | |
// count += (x >= y) ? x : y; | |
if (x >= y) { | |
count += x; | |
} else { | |
count += y; | |
} | |
// | |
} | |
return count; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
605. Can Place Flowers | |
- https://leetcode.com/problems/can-place-flowers/submissions/ | |
class Solution { | |
public boolean canPlaceFlowers(int[] flowerbed, int n) { | |
int count = 0; | |
for(int i = 0; i < flowerbed.length && count < n; i++) { | |
if(flowerbed[i] == 0) { | |
//get next and prev flower bed slot values. If i lies at the ends the next and prev | |
//are considered as 0. | |
int next = (i == flowerbed.length - 1) ? 0 : flowerbed[i + 1]; | |
int prev = (i == 0) ? 0 : flowerbed[i - 1]; | |
if(next == 0 && prev == 0) { | |
flowerbed[i] = 1; | |
count++; | |
} | |
} | |
} | |
return count == n; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Problem Description | |
Given an integer array A, find if an integer p exists in the array such that the number of integers greater than p in the array equals to p. | |
Input Format | |
First and only argument is an integer array A. | |
Output Format | |
Return 1 if any such integer p is found else return -1. | |
Example Input | |
Input 1: | |
A = [3, 2, 1, 3] | |
Input 2: | |
A = [1, 1, 3, 3] | |
Example Output | |
Output 1: | |
1 | |
Output 2: | |
-1 | |
import java.util.ArrayList; | |
import java.util.Collections; | |
public class NextPermutation { | |
public static void main(String[] args) { | |
//A = [3, 2, 1, 3] | |
ArrayList<Integer> a = new ArrayList<Integer>(); | |
a.add(3); | |
a.add(2); | |
a.add(1); | |
a.add(3); | |
System.out.println(solve(a)); | |
} | |
public static int solve(ArrayList<Integer> A) { | |
if (null == A || A.isEmpty()) | |
return 0; | |
Collections.sort(A); | |
int idx = 0; | |
int n = A.size(); | |
while (idx < n) { | |
int num = A.get(idx); | |
while (idx < n && A.get(idx) == num) { | |
idx++; | |
} | |
if (num == A.size() - idx) { | |
return 1; | |
} | |
} | |
return -1; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.array; | |
public class PowXN { | |
/** | |
* https://leetcode.com/problems/powx-n/ | |
* Example 1: | |
* | |
* Input: x = 2.00000, n = 10 Output: 1024.00000 Example 2: | |
* | |
* Input: x = 2.10000, n = 3 Output: 9.26100 Example 3: | |
* | |
* Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = | |
* 0.25 | |
* | |
* @param args | |
*/ | |
public static void main(String[] args) { | |
//slow call | |
System.out.println(pow(2.00000, 10)); | |
System.out.println(pow(2.10000, 3)); | |
System.out.println(pow(2.00000, -2)); | |
// | |
System.out.println("-----------------------------------"); | |
//fast call | |
PowXN pwn=new PowXN(); | |
System.out.println(pwn.pow1(2.00000, 10)); | |
System.out.println(pwn.pow1(2.10000, 3)); | |
System.out.println(pwn.pow1(2.00000, -2)); | |
} | |
// Slow | |
public static double pow(double x, int n) { | |
double pow = 0; | |
double multiply = 1; | |
if (0 == x) | |
return x; | |
// | |
if (n >= 0) { | |
for (int i = 0; i < n; i++) { | |
multiply = multiply * x; | |
} | |
pow = multiply; | |
} else { | |
for (int i = 0; i < n * (-1); i++) { | |
multiply = multiply * x; | |
} | |
pow = 1 / multiply; | |
} | |
return pow; | |
} | |
// fast | |
public double pow1(double x, int n) { | |
if (n >= 0) { | |
return mypow(x, n); | |
} | |
return 1 / mypow(x, n); | |
} | |
double mypow(double x, int n) { | |
if (n == 0) { | |
return 1; | |
} | |
double num = mypow(x, n / 2); | |
if (n % 2 == 0) { | |
return num * num; | |
} | |
return num * num * x; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.array.function; | |
import java.util.Arrays; | |
public class RemoveDuplicate { | |
/* | |
* consecutive Input : geeksforgeeks Output : geksforgeks | |
* | |
*/ | |
static void removeDuplicates(char[] S) | |
{ | |
int n = S.length; | |
// We don't need to do anything for | |
// empty or single character string. | |
if (n < 2) | |
{ | |
return; | |
} | |
// j is used to store index is result | |
// string (or index of current distinct | |
// character) | |
int j = 0; | |
// Traversing string | |
for (int i = 1; i < n; i++) | |
{ | |
// If current character S[i] | |
// is different from S[j] | |
if (S[j] != S[i]) { | |
j++; | |
S[j] = S[i]; | |
/** | |
* e e k s f o r g e e k s =J | |
* g e e k s f o r g e e k s =i | |
*/ | |
} | |
} | |
// | |
for(Character s:S) | |
System.out.println("S="+s); | |
System.out.println("j+1="+j); | |
System.out.println(Arrays.copyOfRange(S, 0, j + 1)); | |
} | |
// Driver code | |
public static void main(String[] args) | |
{ | |
char S1[] = "geeksforgeeks".toCharArray(); | |
removeDuplicates(S1); | |
char S2[] = "aabcca".toCharArray(); | |
removeDuplicates(S2); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
https://www.geeksforgeeks.org/converting-decimal-number-lying-between-1-to-3999-to-roman-numerals/ | |
import java.util.Map; | |
import java.util.TreeMap; | |
public class RomanNumber { | |
private final static TreeMap<Integer, String> map = new TreeMap<Integer, String>(); | |
static { | |
map.put(1000, "M"); | |
map.put(900, "CM"); | |
map.put(500, "D"); | |
map.put(400, "CD"); | |
map.put(100, "C"); | |
map.put(90, "XC"); | |
map.put(50, "L"); | |
map.put(40, "XL"); | |
map.put(10, "X"); | |
map.put(9, "IX"); | |
map.put(5, "V"); | |
map.put(4, "IV"); | |
map.put(1, "I"); | |
} | |
public final static String toRoman(int number) { | |
int key = map.floorKey(number); | |
// | |
if (number == key) { | |
return map.get(number); | |
} | |
return map.get(key) + toRoman(number - key); | |
} | |
public static void main(String args[]) { | |
for (int i = 1; i <= 100; i++) { | |
System.out.println(i + "\t =\t " + RomanNumber.toRoman(i)); | |
} | |
//================================== | |
System.out.println("==="+toRoman(1904)); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Arrays; | |
/** | |
* | |
* {1,2,3}, | |
* {4,5,6}, | |
* {7,8,9} | |
* | |
* [7, 4, 1] | |
* [8, 5, 2] | |
* [9, 6, 3] | |
* | |
* | |
* | |
*/ | |
public class RotateImage { | |
public static void main(String[] args) { | |
// int[][] multiples = new int[4][2];// 4 rows 2 column | |
int[][] matrix = // new int[3][3]; | |
{ { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; | |
rotate(matrix); | |
} | |
public static void rotate(int[][] matrix) { | |
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) { | |
return; | |
} | |
int row = matrix.length; | |
int col = matrix[0].length; | |
// | |
for (int i = 0; i < row / 2; i++) { | |
for (int j = 0; j < col; j++) { | |
swap(matrix, i, j, row - 1 - i, j); | |
} | |
} | |
//[1,2,3], | |
//[4,5,6], | |
//[7,8,9] | |
// | |
//[7, 8, 9], | |
//[4, 5, 6], | |
//[1, 2, 3] | |
// | |
for (int i = 0; i < row; i++) { | |
for (int j = i + 1; j < col; j++) { | |
swap(matrix, i, j, j, i); | |
} | |
} | |
//[7, 4, 1] | |
//[8, 5, 2] | |
//[9, 6, 3] | |
System.out.println("2="+Arrays.deepToString(matrix)); | |
} | |
private static void swap(int[][] matrix, int x0, int y0, int x1, int y1) { | |
int temp = matrix[x0][y0]; | |
matrix[x0][y0] = matrix[x1][y1]; | |
matrix[x1][y1] = temp; | |
} | |
} | |
// /* | |
// * clockwise rotate | |
// * first reverse up to down, then swap the symmetry | |
// * 1 2 3 7 8 9 7 4 1 | |
// * 4 5 6 => 4 5 6 => 8 5 2 | |
// * 7 8 9 1 2 3 9 6 3 | |
// */ | |
// void rotate(vector<vector<int> > &matrix) { | |
// reverse(matrix.begin(), matrix.end()); | |
// for (int i = 0; i < matrix.size(); ++i) { | |
// for (int j = i + 1; j < matrix[i].size(); ++j) | |
// swap(matrix[i][j], matrix[j][i]); | |
// } | |
// } | |
// /* | |
// * anticlockwise rotate | |
// * first reverse left to right, then swap the symmetry | |
// * 1 2 3 3 2 1 3 6 9 | |
// * 4 5 6 => 6 5 4 => 2 5 8 | |
// * 7 8 9 9 8 7 1 4 7 | |
// */ | |
// void anti_rotate(vector<vector<int> > &matrix) { | |
// for (auto vi : matrix) reverse(vi.begin(), vi.end()); | |
// for (int i = 0; i < matrix.size(); ++i) { | |
// for (int j = i + 1; j < matrix[i].size(); ++j) | |
// swap(matrix[i][j], matrix[j][i]); | |
// } | |
// } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
static void rotate(ArrayList<ArrayList<Integer>> a) { | |
if (null != a && !a.isEmpty()) | |
return; | |
// | |
int N = a.size() - 1; | |
// | |
for (int i = 0; i < a.size() / 2; i++) { | |
for (int j = i; j < N - i; j++) { | |
int temp1 = a.get(N - j).get(i); | |
int temp2 = a.get(N - i).get(N - j); | |
int temp3 = a.get(j).get(N - i); | |
int temp4 = a.get(i).get(j); | |
a.get(i).set(j, temp1); | |
a.get(N - j).set(i, temp2); | |
a.get(N - i).set(N - j, temp3); | |
a.get(j).set(N - i, temp4); | |
} | |
} | |
} | |
public static void main(String[] args) { | |
ArrayList<ArrayList<Integer>> A = new ArrayList<ArrayList<Integer>>(); | |
ArrayList<Integer> temp = new ArrayList<Integer>(); | |
temp.add(1); | |
temp.add(2); | |
temp.add(3); | |
temp.add(4); | |
A.add(new ArrayList<Integer>(temp)); | |
temp.clear(); | |
temp.add(5); | |
temp.add(6); | |
temp.add(7); | |
temp.add(8); | |
A.add(new ArrayList<Integer>(temp)); | |
temp.clear(); | |
temp.add(9); | |
temp.add(10); | |
temp.add(11); | |
temp.add(12); | |
A.add(new ArrayList<Integer>(temp)); | |
temp.clear(); | |
temp.add(13); | |
temp.add(14); | |
temp.add(15); | |
temp.add(16); | |
A.add(new ArrayList<Integer>(temp)); | |
temp.clear(); | |
for (ArrayList<Integer> t : A) | |
System.out.println(t); | |
rotate(A); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.HashSet; | |
//https://www.geeksforgeeks.org/smallest-string-which-not-a-subsequence-of-the-given-string/ | |
public class SubSequenceString { | |
static String ShortestSubsequenceNotPresent(String str) { | |
// Stores the shortest string which is not a subsequence of the given string | |
String shortestString = ""; | |
// Stores length of string | |
int N = str.length(); | |
// Stores distinct character of subsegments | |
HashSet<Character> subsegments = new HashSet<>(); | |
// Traverse the given string | |
for (int i = 0; i < N; i++) { | |
// Insert current character | |
// into subsegments | |
subsegments.add(str.charAt(i)); | |
// If all lowercase alphabets present in the subsegment | |
if (subsegments.size() == 26) { | |
// Insert the last character of | |
// subsegment into shortestString | |
shortestString = shortestString + str.charAt(i); | |
// Remove all elements from | |
// the current subsegment | |
subsegments.clear(); | |
} | |
} | |
// Traverse all lowercase alphabets | |
for (char ch = 'a'; ch <= 'z'; ch++) { | |
// If current character is not | |
// present in the subsegment | |
if (!subsegments.contains(ch)) { | |
shortestString = shortestString + ch; | |
// Return shortestString | |
return shortestString; | |
} | |
} | |
return shortestString; | |
} | |
// Driver Code | |
public static void main(String[] args) { | |
String str = "abcdefghijklmnopqrstuvwxyzaabbccdd"; | |
System.out.println(ShortestSubsequenceNotPresent(str)); | |
//System.out.println(ShortestSubsequenceNotPresent("abaabcc")); | |
//sSystem.out.println(ShortestSubsequenceNotPresent("a")); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Complete the superReducedString function below. | |
static String superReducedString(String s) { | |
char[] ch = s.toCharArray(); | |
Stack<Character> st = new Stack<Character>(); | |
// | |
for (int i = 0; i < ch.length; i++) { | |
if (st.empty()) { | |
st.push(ch[i]); | |
} else if (st.peek() == ch[i]) { | |
st.pop(); | |
} else { | |
st.push(ch[i]); | |
} | |
} | |
// | |
String str = ""; | |
while (!st.isEmpty()) { | |
str = st.pop() + str; | |
} | |
return str==""?"Empty String" :str; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
- https://leetcode.com/problems/third-maximum-number/ | |
/** | |
* 414. Third Maximum Number | |
* | |
* Given a non-empty array of integers, return the third maximum number in this array. | |
* If it does not exist, return the maximum number. The time complexity must be in O(n). | |
Example 1: | |
Input: [3, 2, 1] | |
Output: 1 | |
Explanation: The third maximum is 1. | |
Example 2: | |
Input: [1, 2] | |
Output: 2 | |
Explanation: The third maximum does not exist, so the maximum (2) is returned instead. | |
Example 3: | |
Input: [2, 2, 3, 1] | |
Output: 1 | |
Explanation: Note that the third maximum here means the third maximum distinct number. | |
Both numbers with value 2 are both considered as second maximum. | |
*/ | |
public class _414 { | |
public int thirdMax(int[] nums) { | |
long max1 = Long.MIN_VALUE; | |
long max2 = Long.MIN_VALUE; | |
long max3 = Long.MIN_VALUE; | |
for (int i : nums) { | |
max1 = Math.max(max1, i); | |
} | |
for (int i : nums) { | |
if (i == max1) { | |
continue; | |
} | |
max2 = Math.max(max2, i); | |
} | |
for (int i : nums) { | |
if (i == max1 || i == max2) { | |
continue; | |
} | |
max3 = Math.max(max3, i); | |
} | |
return (int) (max3 == Long.MIN_VALUE ? max1 : max3); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Arrays; | |
public class TransposeMatrix { | |
/** | |
* [1 2 3] | |
* [4 5 6] | |
* [7 8 9] | |
* Transpose Matrix | |
* [1 4 7] | |
* [2 5 8] | |
* [3 6 9] | |
* @param args | |
*/ | |
public static void main(String[] args) { | |
//int[][] multiples = new int[4][2];// 4 rows 2 column | |
int[][] matrix = //new int[3][3]; | |
{ | |
{1,2,3}, | |
{4,5,6}, | |
{7,8,9} | |
}; | |
int[][] arr = transpose(matrix); | |
// | |
System.out.println(Arrays.deepToString(arr)); | |
} | |
static int [][] transpose(int [][] A){ | |
int row =A.length; | |
int column=A[0].length; | |
//swap | |
int newMatrix[][]= new int[column][row]; | |
for(int i=0;i<row;i++) { | |
for(int j=0;j<column;j++) { | |
//System.out.println(A[i][j]); | |
newMatrix[j][i]=A[i][j]; | |
} | |
} | |
return newMatrix; | |
} | |
static int[][] transpose1(int[][] A) { | |
int row = A.length; | |
int column = A[0].length; | |
int[][] newMatrix = new int[column][row]; | |
// | |
for (int r = 0; r < row; ++r) | |
for (int c = 0; c < column; ++c) { | |
newMatrix[c][r] = A[r][c]; | |
} | |
return newMatrix; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
https://www.interviewbit.com/problems/wave-array/ | |
import java.util.ArrayList; | |
import java.util.Collections; | |
public class WaveArray { | |
public static void main(String[] args) { | |
// 1, 2, 3, 4 | |
ArrayList<Integer> list = new ArrayList(); | |
list.add(1); | |
list.add(2); | |
list.add(3); | |
list.add(4); | |
// | |
//One possible answer : [2, 1, 4, 3] | |
//Another possible answer : [4, 1, 3, 2] | |
System.out.println(wave(list).toString()); | |
} | |
//a1 >= a2 <= a3 >= a4 <= a5. | |
public static ArrayList<Integer> wave(ArrayList<Integer> A) { | |
if (null != A && A.isEmpty()) | |
return A; | |
// | |
Collections.sort(A); | |
// | |
for (int i = 0; i < A.size()-1; i+=2) { | |
int temp = A.get(i); | |
A.set(i, A.get(i + 1)); | |
A.set(i + 1, temp); | |
} | |
// | |
return A; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
- https://gist.github.com/nickmyself | |
- https://tenderleo.gitbooks.io/leetcode-solutions-/content | |
- https://gist.github.com/BiruLyu | |
- https://github.com/gouthampradhan/leetcode | |
- https://github.com/fluency03/leetcode-java | |
- https://www.codebycase.com/algorithms/a02-arrays-and-strings.html |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment