Skip to content

Commit 0777240

Browse files
gouthampradhangouthampradhan
committed
Solved Problems
1 parent ab16d63 commit 0777240

5 files changed

Lines changed: 317 additions & 0 deletions

File tree

‎problems/src/array/AddToArrayFormOfInteger.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package heap;
2+
import java.math.BigInteger;
3+
import java.util.*;
4+
/**
5+
* Created by gouthamvidyapradhan on 25/07/2019
6+
*/
7+
public class Task1 {
8+
public static void main(String[] args) {
9+
//
10+
}
11+
12+
public List<Integer> addToArrayForm(int[] A, int K) {
13+
StringBuilder sb = new StringBuilder();
14+
for(int a : A){
15+
sb.append(a);
16+
}
17+
BigInteger big = new BigInteger(sb.toString());
18+
BigInteger result = big.add(BigInteger.valueOf(K));
19+
String resultStr = result.toString();
20+
List<Integer> list = new ArrayList<>();
21+
for(char a : resultStr.toCharArray()){
22+
list.add(Integer.parseInt(String.valueOf(a)));
23+
}
24+
return list;
25+
}
26+
}

‎problems/src/depth_first_search/SatisfiabilityOfEquations.java‎

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
package heap;
2+
import java.util.*;
3+
/**
4+
* Created by gouthamvidyapradhan on 25/07/2019 Given an array equations of strings that represent
5+
* relationships between variables, each string equations[i] has length 4 and takes one of two
6+
* different forms: "a==b" or "a!=b". Here, a and b are lowercase letters (not necessarily
7+
* different) that represent one-letter variable names.
8+
*
9+
* <p>Return true if and only if it is possible to assign integers to variable names so as to
10+
* satisfy all the given equations.
11+
*
12+
* <p>Example 1:
13+
*
14+
* <p>Input: ["a==b","b!=a"] Output: false Explanation: If we assign say, a = 1 and b = 1, then the
15+
* first equation is satisfied, but not the second. There is no way to assign the variables to
16+
* satisfy both equations. Example 2:
17+
*
18+
* <p>Input: ["b==a","a==b"] Output: true Explanation: We could assign a = 1 and b = 1 to satisfy
19+
* both equations. Example 3:
20+
*
21+
* <p>Input: ["a==b","b==c","a==c"] Output: true Example 4:
22+
*
23+
* <p>Input: ["a==b","b!=c","c==a"] Output: false Example 5:
24+
*
25+
* <p>Input: ["c==c","b==d","x!=z"] Output: true
26+
*
27+
* <p>Note:
28+
*
29+
* <p>1 <= equations.length <= 500 equations[i].length == 4 equations[i][0] and equations[i][3] are
30+
* lowercase letters equations[i][1] is either '=' or '!' equations[i][2] is '='
31+
*
32+
* Solution: O(N) For all the equations which are of the form 'a==b' form a graph of connected components. Start
33+
* assigning values to each of the connected components. All the nodes in the connected components should have the
34+
* same value assigned - If any of the connected components fails this criteria
35+
* then return false.
36+
*/
37+
public class Task2 {
38+
public static void main(String[] args) {
39+
String[] input = {"c==c","f!=a","f==b","b==c"};
40+
System.out.println(new Task2().equationsPossible(input));
41+
}
42+
43+
private Set<Character> done;
44+
private Map<Character, Integer> valueMap;
45+
private int count = 0;
46+
public boolean equationsPossible(String[] equations) {
47+
Map<Character, List<Character>> graph = new HashMap<>();
48+
done = new HashSet<>();
49+
valueMap = new HashMap<>();
50+
for(String eq : equations){
51+
if(eq.charAt(1) == '='){
52+
graph.putIfAbsent(eq.charAt(0), new ArrayList<>());
53+
graph.get(eq.charAt(0)).add(eq.charAt(3));
54+
graph.putIfAbsent(eq.charAt(3), new ArrayList<>());
55+
graph.get(eq.charAt(3)).add(eq.charAt(0));
56+
57+
}
58+
}
59+
for(char c : graph.keySet()){
60+
if(!done.contains(c)){
61+
dfs(c, graph, ++count);
62+
}
63+
}
64+
65+
for(String eq : equations){
66+
if(eq.charAt(1) == '!'){
67+
char a = eq.charAt(0);
68+
char b = eq.charAt(3);
69+
if(a == b) return false;
70+
if(valueMap.containsKey(a) && valueMap.containsKey(b)){
71+
if(valueMap.get(a).intValue() == valueMap.get(b).intValue()){
72+
return false;
73+
}
74+
}
75+
}
76+
}
77+
return true;
78+
}
79+
80+
81+
private boolean dfs(char node, Map<Character, List<Character>> graph, int value){
82+
done.add(node);
83+
valueMap.put(node, value);
84+
List<Character> children = graph.get(node);
85+
if(!children.isEmpty()){
86+
for(char c : children){
87+
if(!done.contains(c)){
88+
boolean status = dfs(c, graph, value);
89+
if(!status) {
90+
return status;
91+
}
92+
} else{
93+
if(valueMap.get(c) != value){
94+
return false;
95+
}
96+
}
97+
}
98+
}
99+
return true;
100+
}
101+
102+
}

‎problems/src/greedy/BrokenCalculator.java‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package heap;
2+
import java.util.*;
3+
/**
4+
* Created by gouthamvidyapradhan on 25/07/2019 On a broken calculator that has a number showing on
5+
* its display, we can perform two operations:
6+
*
7+
* <p>Double: Multiply the number on the display by 2, or; Decrement: Subtract 1 from the number on
8+
* the display. Initially, the calculator is displaying the number X.
9+
*
10+
* <p>Return the minimum number of operations needed to display the number Y.
11+
*
12+
* <p>Example 1:
13+
*
14+
* <p>Input: X = 2, Y = 3 Output: 2 Explanation: Use double operation and then decrement operation
15+
* {2 -> 4 -> 3}. Example 2:
16+
*
17+
* <p>Input: X = 5, Y = 8 Output: 2 Explanation: Use decrement and then double {5 -> 4 -> 8}.
18+
* Example 3:
19+
*
20+
* <p>Input: X = 3, Y = 10 Output: 3 Explanation: Use double, decrement and double {3 -> 6 -> 5 ->
21+
* 10}. Example 4:
22+
*
23+
* <p>Input: X = 1024, Y = 1 Output: 1023 Explanation: Use decrement operations 1023 times.
24+
*
25+
* <p>Note:
26+
*
27+
* <p>1 <= X <= 10^9 1 <= Y <= 10^9
28+
*
29+
* Solution: O(log Y) Arrive at the solution by working backwards starting from Y.
30+
* General idea is as follows.
31+
* If Y is even then find the minimum steps required to arrive at Y by finding the quotient after dividing by 2. If Y
32+
* is odd then find the minimum steps required to arrive at Y + 1 (even number) + 1 (to move backwards)
33+
*/
34+
public class BrokenCalculator {
35+
public static void main(String[] args) {
36+
//
37+
}
38+
39+
public int brokenCalc(int X, int Y) {
40+
if(X == Y) return 0;
41+
else if(Y < X) return X - Y;
42+
else {
43+
int count = 0;
44+
while(Y > X){
45+
if(Y % 2 == 0){
46+
Y /= 2;
47+
count++;
48+
} else{
49+
Y += 1;
50+
Y /= 2;
51+
count+=2;
52+
}
53+
}
54+
if(X == Y) return count;
55+
else return count + (X - Y);
56+
}
57+
}
58+
}

‎problems/src/string/PushDominoes.java‎

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
package math;
2+
import java.util.*;
3+
/**
4+
* Created by gouthamvidyapradhan on 24/07/2019 There are N dominoes in a line, and we place each
5+
* domino vertically upright.
6+
*
7+
* <p>In the beginning, we simultaneously push some of the dominoes either to the left or to the
8+
* right.
9+
*
10+
* <p>After each second, each domino that is falling to the left pushes the adjacent domino on the
11+
* left.
12+
*
13+
* <p>Similarly, the dominoes falling to the right push their adjacent dominoes standing on the
14+
* right.
15+
*
16+
* <p>When a vertical domino has dominoes falling on it from both sides, it stays still due to the
17+
* balance of the forces.
18+
*
19+
* <p>For the purposes of this question, we will consider that a falling domino expends no
20+
* additional force to a falling or already fallen domino.
21+
*
22+
* <p>Given a string "S" representing the initial state. S[i] = 'L', if the i-th domino has been
23+
* pushed to the left; S[i] = 'R', if the i-th domino has been pushed to the right; S[i] = '.', if
24+
* the i-th domino has not been pushed.
25+
*
26+
* <p>Return a string representing the final state.
27+
*
28+
* <p>Example 1:
29+
*
30+
* <p>Input: ".L.R...LR..L.." Output: "LL.RR.LLRRLL.." Example 2:
31+
*
32+
* <p>Input: "RR.L" Output: "RR.L" Explanation: The first domino expends no additional force on the
33+
* second domino. Note:
34+
*
35+
* <p>0 <= N <= 10^5 String dominoes contains only 'L', 'R' and '.'
36+
*/
37+
public class Task2 {
38+
public static void main(String[] args) {
39+
System.out.println(new Task2().pushDominoes("RR.L"));
40+
}
41+
42+
public String pushDominoes(String dominoes) {
43+
int R = -1, L = -1;
44+
char[] A = dominoes.toCharArray();
45+
for(int i = 0; i < A.length; i ++){
46+
if(A[i] == 'L'){
47+
if(R > L){
48+
int d = (i - R);
49+
int st;
50+
st = R + d/2;
51+
if((d % 2) == 0){
52+
A[st] = '.';
53+
}
54+
for(int j = st + 1; j < i; j ++){
55+
A[j] = 'L';
56+
}
57+
} else{
58+
for(int j = (L == -1 ? 0 : L); j < i; j ++){
59+
A[j] = 'L';
60+
}
61+
}
62+
L = i;
63+
} else {
64+
if(A[i] == 'R'){
65+
R = i;
66+
} else{
67+
if(R > L){
68+
A[i] = 'R';
69+
}
70+
}
71+
}
72+
}
73+
return String.valueOf(A);
74+
}
75+
}

‎problems/src/two_pointers/SubarraysWithKDifferentIntegers.java‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package two_pointers;
2+
/**
3+
* Created by gouthamvidyapradhan on 25/07/2019 Given an array A of positive integers, call a
4+
* (contiguous, not necessarily distinct) subarray of A good if the number of different integers in
5+
* that subarray is exactly K.
6+
*
7+
* <p>(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)
8+
*
9+
* <p>Return the number of good subarrays of A.
10+
*
11+
* <p>Example 1:
12+
*
13+
* <p>Input: A = [1,2,1,2,3], K = 2 Output: 7 Explanation: Subarrays formed with exactly 2 different
14+
* integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]. Example 2:
15+
*
16+
* <p>Input: A = [1,2,1,3,4], K = 3 Output: 3 Explanation: Subarrays formed with exactly 3 different
17+
* integers: [1,2,1,3], [2,1,3], [1,3,4].
18+
*
19+
* <p>Note:
20+
*
21+
* <p>1 <= A.length <= 20000 1 <= A[i] <= A.length 1 <= K <= A.length
22+
* Solution: O(N) General idea is to find subarraysWithKDistinct(A, atMost(K)) - subarraysWithKDistinct(A, atMost(K -
23+
* 1)).
24+
*/
25+
public class Task4 {
26+
public static void main(String[] args) {
27+
int[] A = {1,2,1,2,3};
28+
Task4 task = new Task4();
29+
System.out.println(task.subarraysWithKDistinct(A, 2));
30+
}
31+
32+
public int subarraysWithKDistinct(int[] A, int K) {
33+
return calculate(A, K) - calculate(A, K - 1);
34+
}
35+
36+
private int calculate(int[] A, int K) {
37+
int count = 0;
38+
int[] frequency = new int[A.length + 1];
39+
int currCount = 0;
40+
for(int i = 0, j = 0; i < A.length; i ++){
41+
frequency[A[i]]++;
42+
if(frequency[A[i]] == 1){
43+
currCount ++;
44+
}
45+
while(currCount > K){
46+
frequency[A[j]]--;
47+
if(frequency[A[j]] == 0){
48+
currCount --;
49+
}
50+
j++;
51+
}
52+
count += (i - j + 1);
53+
}
54+
return count;
55+
}
56+
}

0 commit comments

Comments
 (0)