Skip to content

Commit f731e4e

Browse files
thuva4thuva4
authored
Merge branch 'master' into master
2 parents 9fdb2ef + 2b208c2 commit f731e4e

File tree

15 files changed

+823
-15
lines changed

15 files changed

+823
-15
lines changed

‎BinaryGCD/Java/BinaryGCD.java‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
/**
2+
* The binary GCD algorithm, also known as Stein's algorithm, is an algorithm
3+
* that computes the greatest common divisor of two nonnegative integers.
4+
*
5+
* @author Atom
6+
* @see <a href="https://en.wikipedia.org/wiki/Binary_GCD_algorithm">Binary GCD algorithm</a>
7+
* @see <a href="http://www.geeksforgeeks.org/steins-algorithm-for-finding-gcd/">Stein’s Algorithm for finding GCD</a>
8+
*/
9+
public class BinaryGCD {
10+
11+
/**
12+
* Stein's algorithm uses simpler arithmetic operations than the conventional Euclidean algorithm,
13+
* replaces division with arithmetic shifts, comparisons, and subtraction
14+
*
15+
* @param a
16+
* @param b
17+
* @return
18+
*/
19+
public static int gcd(int a, int b) {
20+
// gcd(0,b) == b; gcd(a,0) == a, gcd(0,0) == 0
21+
if (a == 0) { return b; }
22+
if (b == 0) { return a; }
23+
24+
// find the greatest power of 2 dividing both 'a' and 'b'
25+
int shift;
26+
for (shift = 0; ((a | b) & 1) == 0; shift++) {
27+
a >>>= 1;
28+
b >>>= 1;
29+
}
30+
31+
// divide 'a' by 2 until 'a' becomes odd
32+
while ((a & 1) == 0) { a >>>= 1; }
33+
34+
// from here on, 'a' is always odd
35+
while (b != 0) {
36+
// remove all factor of 2 in 'b'
37+
while ((b & 1) == 0) { b >>>= 1; }
38+
// Now 'a' and 'b' are both odd. If 'a' > 'b' swap, substract 'a' from 'b'
39+
if (a > b) {
40+
int tmp = a;
41+
a = b;
42+
b = tmp;
43+
}
44+
b -= a;
45+
}
46+
// restore common factors of 2
47+
return a << shift;
48+
}
49+
50+
public static void main(String[] args) {
51+
System.out.println(gcd(10, 5));
52+
System.out.println(gcd(5, 10));
53+
System.out.println(gcd(10, 8));
54+
System.out.println(gcd(8, 2));
55+
System.out.println(gcd(7000, 2000));
56+
System.out.println(gcd(2000, 7000));
57+
System.out.println(gcd(10, 11));
58+
System.out.println(gcd(11, 7));
59+
System.out.println(gcd(239, 293));
60+
}
61+
62+
}
63+

‎BinarySearch/Swift/BinarySearch.swift‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
/**
2+
Binary Search
3+
4+
5+
Recursively splits the array in half until the value is found.
6+
7+
If there is more than one occurrence of the search key in the array, then
8+
there is no guarantee which one it finds.
9+
10+
Note: The array must be sorted!
11+
You can find the documentation on https://www.raywenderlich.com/139821/swift-algorithm-club-swift-binary-search-tree-data-structure]
12+
**/
13+
14+
import Foundation
15+
16+
// The recursive version of binary search.
17+
18+
public func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
19+
if range.lowerBound >= range.upperBound {
20+
return nil
21+
} else {
22+
let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
23+
if a[midIndex] > key {
24+
return binarySearch(a, key: key, range: range.lowerBound ..< midIndex)
25+
} else if a[midIndex] < key {
26+
return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound)
27+
} else {
28+
return midIndex
29+
}
30+
}
31+
}
32+
33+
/**
34+
The iterative version of binary search.
35+
36+
Notice how similar these functions are. The difference is that this one
37+
uses a while loop, while the other calls itself recursively.
38+
**/
39+
40+
public func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? {
41+
var lowerBound = 0
42+
var upperBound = a.count
43+
while lowerBound < upperBound {
44+
let midIndex = lowerBound + (upperBound - lowerBound) / 2
45+
if a[midIndex] == key {
46+
return midIndex
47+
} else if a[midIndex] < key {
48+
lowerBound = midIndex + 1
49+
} else {
50+
upperBound = midIndex
51+
}
52+
}
53+
return nil
54+
}

‎CONTRIBUTING.md‎

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -72,12 +72,13 @@ Unfortunately, sometimes the bug can be only reproduced in your project or in yo
7272
- [r-o-k-u-r-o-u](https://github.com/r-o-k-u-r-o-u)
7373
- [pabe94](https://github.com/pabe94)
7474
- [IshamMohamed](https://github.com/IshamMohamed)
75+
7576
- [maaz93](https://github.com/maaz93)
7677
- [melzareix](https://github.com/melzareix)
7778
- [causztic](https://github.com/causztic)
7879
- [ranjanbinwani](https://github.com/ranjanbinwani)
7980
- [buihaduong](https://github.com/buihaduong)
80-
- [Texla](https://github.com/Texla)
81+
-- [Texla](https://github.com/Texla)
8182
- [prateekpandey14](https://github.com/prateekpandey14)
8283
- [riktimmondal](https://github.com/riktimmondal)
8384
- [C2P1](https://github.com/C2P1)
@@ -137,4 +138,11 @@ Unfortunately, sometimes the bug can be only reproduced in your project or in yo
137138
- [SrGrace](https://github.com/SrGrace)
138139
- [d-grossman](https://github.com/d-grossman)
139140
- [javmonisu](https://github.com/javmonisu)
141+
- [lena15n](https://github.com/lena15n)
142+
- [stripedpajamas](https://github.com/stripedpajamas)
143+
- [Renan Vichetti](https://github.com/rvconessa)
144+
- [pranjalrai](https://github.com/pranjalrai)
145+
- [stuxxnet](https://github.com/stuxxnet42)
146+
- [BurnzZ](https://github.com/BurnzZ)
147+
- [FernandaOchoa](https://github.com/FernandaOchoa)
140148
- [npcoder2k14](https://github.com/npcoder2k14)

‎Doomsday/cpp/doomsday.cpp‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
#include <iostream>
2+
#include <string>
3+
4+
int dayOfWeek(int y, int m, int d){
5+
int t[]={0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
6+
y -= (m<3) ? 1 : 0;
7+
return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
8+
}
9+
10+
int main(int argc, char** argv){
11+
if(argc != 4){
12+
std::cout<<"usage is: program YYYY MM DD"<<std::endl;
13+
return -1;
14+
}
15+
int year=std::stoi(argv[1]);
16+
int month=std::stoi(argv[2]);
17+
int day=std::stoi(argv[3]);
18+
std::string days[7]={"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
19+
std::cout<<days[dayOfWeek(year, month, day)]<<std::endl;
20+
return 0;
21+
}

‎EdmondsKarp/Java/EdmondsKarp.java‎

Lines changed: 199 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,199 @@
1+
import java.util.*;
2+
3+
public class EdmondsKarp {
4+
public static void main(String[] args) {
5+
int verticesCount = 6;
6+
double[][] capacity = initCapacity(verticesCount);
7+
int s = 0;
8+
int t = verticesCount - 1;
9+
Map<Integer, List<Edge>> graphForwardEdges = initForwardGraphEdges();
10+
Map<Integer, List<Edge>> graphReverseEdges = initReverseGraphEdges();
11+
12+
double maxFlow = calculateMaxFlow(graphForwardEdges, graphReverseEdges, s, t, capacity);
13+
System.out.println(maxFlow);
14+
}
15+
16+
private static double calculateMaxFlow(Map<Integer, List<Edge>> graphForwardEdges,
17+
Map<Integer, List<Edge>> graphReverseEdges,
18+
int s, int t, double[][] capacity) {
19+
int verticesCount = graphForwardEdges.size();
20+
double[][] flow = new double[verticesCount][verticesCount];
21+
double maxFlow = 0.0;
22+
boolean isPathExist = true;
23+
Deque<Integer> queue = new ArrayDeque<>();
24+
25+
while (isPathExist) {
26+
Edge[] parent = new Edge[verticesCount];
27+
boolean[] visited = new boolean[verticesCount];
28+
queue.addLast(s);
29+
30+
// choose path from s to t
31+
while (!queue.isEmpty()) {
32+
int currentVertex = queue.pollFirst();
33+
visited[currentVertex] = true;
34+
List<Edge> outEdges = graphForwardEdges.get(currentVertex);
35+
36+
for (Edge edge : outEdges) {
37+
int to = edge.getTo();
38+
if (!visited[to]) {
39+
if (capacity[currentVertex][to] - flow[currentVertex][to] > 0 &&
40+
flow[currentVertex][to] >= 0) {
41+
parent[to] = edge;
42+
queue.addLast(to);
43+
}
44+
}
45+
}
46+
47+
List<Edge> inEdges = graphReverseEdges.get(currentVertex);
48+
for (Edge edge : inEdges) {
49+
int from = edge.getFrom();
50+
if (!visited[from]) {
51+
if (flow[from][currentVertex] > 0) {
52+
parent[from] = edge;
53+
queue.addLast(from);
54+
}
55+
}
56+
}
57+
}
58+
59+
isPathExist = visited[t];
60+
61+
// find max possible flow of the chosen path
62+
if (isPathExist) {
63+
int child = t;
64+
double bottleneck = Double.MAX_VALUE;
65+
66+
while (child != s) {
67+
Edge edge = parent[child];
68+
if (!edge.isReverse()) {
69+
bottleneck = Math.min(bottleneck, capacity[edge.getFrom()][edge.getTo()] -
70+
flow[edge.getFrom()][edge.getTo()]);
71+
} else {
72+
bottleneck = Math.min(bottleneck, flow[edge.getFrom()][edge.getTo()]);
73+
}
74+
75+
child = edge.isReverse() ? edge.getTo() : edge.getFrom();
76+
}
77+
78+
// update flow
79+
maxFlow += bottleneck;
80+
child = t;
81+
while (child != s) {
82+
Edge edge = parent[child];
83+
int from = (!edge.isReverse()) ? edge.getFrom() : edge.getTo();
84+
flow[from][child] += bottleneck;
85+
flow[child][from] -= bottleneck;
86+
child = (!edge.isReverse()) ? edge.getFrom() : edge.getTo();
87+
}
88+
}
89+
}
90+
91+
return maxFlow;
92+
}
93+
94+
private static double[][] initCapacity(int verticesCount) {
95+
double[][] capacity = new double[verticesCount][verticesCount];
96+
capacity[0][1] = 10;
97+
capacity[1][0] = 10;
98+
99+
capacity[0][3] = 10;
100+
capacity[3][0] = 10;
101+
102+
103+
capacity[1][2] = 4;
104+
capacity[2][1] = 4;
105+
106+
capacity[1][3] = 2;
107+
capacity[3][1] = 2;
108+
109+
capacity[1][4] = 8;
110+
capacity[4][1] = 8;
111+
112+
113+
capacity[2][5] = 10;
114+
capacity[5][2] = 10;
115+
116+
117+
capacity[3][4] = 9;
118+
capacity[4][3] = 9;
119+
120+
121+
capacity[4][2] = 6;
122+
capacity[2][4] = 6;
123+
124+
capacity[4][5] = 10;
125+
capacity[5][4] = 10;
126+
127+
return capacity;
128+
}
129+
130+
private static Map<Integer, List<Edge>> initForwardGraphEdges() {
131+
Map<Integer, List<Edge>> graph = new HashMap<>();
132+
graph.put(0, createForwardEdges(0, 1, 3));
133+
graph.put(1, createForwardEdges(1, 2, 3, 4));
134+
graph.put(2, createForwardEdges(2, 5));
135+
graph.put(3, createForwardEdges(3, 4));
136+
graph.put(4, createForwardEdges(4, 2, 5));
137+
graph.put(5, Collections.emptyList());
138+
139+
return graph;
140+
}
141+
142+
private static Map<Integer, List<Edge>> initReverseGraphEdges() {
143+
Map<Integer, List<Edge>> graph = new HashMap<>();
144+
graph.put(0, Collections.emptyList());
145+
graph.put(1, Collections.emptyList());
146+
graph.put(2, createReverseEdges(2, 1, 4));
147+
graph.put(3, createReverseEdges(3, 1));
148+
graph.put(4, createReverseEdges(4, 1, 3));
149+
graph.put(5, Collections.emptyList());
150+
151+
return graph;
152+
}
153+
154+
private static List<Edge> createForwardEdges(int from, Integer... toVertices) {
155+
List<Edge> edges = new ArrayList<>();
156+
157+
for (Integer to : toVertices) {
158+
Edge edge = new Edge(from, to, false);
159+
edges.add(edge);
160+
}
161+
162+
return edges;
163+
}
164+
165+
private static List<Edge> createReverseEdges(int to, Integer... fromVertices) {
166+
List<Edge> edges = new ArrayList<>();
167+
168+
for (Integer from : fromVertices) {
169+
Edge edge = new Edge(from, to, true);
170+
edges.add(edge);
171+
}
172+
173+
return edges;
174+
}
175+
176+
private static class Edge {
177+
private int from;
178+
private int to;
179+
private boolean isReverse;
180+
181+
Edge(int from, int to, boolean isReverse) {
182+
this.from = from;
183+
this.to = to;
184+
this.isReverse = isReverse;
185+
}
186+
187+
int getFrom() {
188+
return from;
189+
}
190+
191+
int getTo() {
192+
return to;
193+
}
194+
195+
boolean isReverse() {
196+
return isReverse;
197+
}
198+
}
199+
}

‎Fibonacci/Python/fibonacci_golden_ratio.py‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
import math
2+
3+
def fibonacci_golden_ratio(num):
4+
"""Returns fibonacci numbers using the Golden Ratio formula"""
5+
6+
golden_ratio = (1 + math.sqrt(5)) / 2
7+
8+
golden_ratio_conjugate = (1 - math.sqrt(5)) / 2
9+
10+
return int(round(
11+
((golden_ratio ** num)
12+
- (golden_ratio_conjugate ** num))
13+
/ math.sqrt(5)))

‎HammingDistance/Go/hammingDistance.go‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
package hammingDistance
2+
3+
func HammingDistance(a, b string) int {
4+
if len(a) != len(b) {
5+
panic("The two strings must have equal length")
6+
}
7+
aRunes := []rune(a)
8+
bRunes := []rune(b)
9+
distance := 0
10+
for i, r := range aRunes {
11+
if r != bRunes[i] {
12+
distance++
13+
}
14+
}
15+
return distance
16+
}

0 commit comments

Comments
 (0)