-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRecursion2.java
More file actions
134 lines (118 loc) · 3.44 KB
/
Recursion2.java
File metadata and controls
134 lines (118 loc) · 3.44 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/*
// tiling problem.....
public class Recursion2 {
public static int numTilings(int n) {
//base cse
if(n==0||n==1){
return 1;
}
//vertical
int fnm1 = numTilings(n-1);
// horizontal
int fnm2 = numTilings(n-2);
int totWays = fnm1+fnm2;
return totWays;
}
public static void main(String[] args) {
System.out.println(numTilings (3));
}
}
*/
/*
// Remove duplicate in string
public class Recursion2 {
public static void removeDupl(String str, int idx,StringBuilder newStr,boolean Map[]){
if(idx == str.length()){
System.out.println(newStr);
return;
}
char currChar = str.charAt(idx);
if(Map[currChar-'a']== true){
removeDupl(str, idx+1, newStr, Map);
}else{
Map[currChar-'a'] = true;
removeDupl(str, idx+1, newStr.append(currChar ), Map);
}
}
public static void main(String[] args) {
String str = "appnacollege";
removeDupl(str, 0, new StringBuilder(""), new boolean[26]);
}
}
*/
/* friends pair problem...
public class Recursion2 {
public static int countFriendsPairings(int n) {
// code here
if(n==1 || n==2){
return n;
}
int fnm1 = countFriendsPairings(n-1);
int fnm2 = countFriendsPairings(n-2);
int pairWays = (n-1)* fnm2;
int totalways = fnm1 + pairWays;
return totalways;
}
public static void main(String[] args) {
System.out.println(countFriendsPairings(3));
}
}
*/
/* binary string problem..
public class Recursion2 {
public static void printBinaryString(int n, int lastPlace,String str){
if(n==0){
System.out.println(str);
return;
}
if(lastPlace==0){
printBinaryString(n-1, 0, str+"0");
printBinaryString(n-1, 1, str+"1");
}
else{
printBinaryString(n-1, 0, str+"0");
}
}
public static void main(String[] args) {
printBinaryString(3, 0, "");
}
}
*/
// towe of hanoi
public class Recursion2 {
public static void towerOfHanoi(int n, String src, String helper, String dest) {
if (n == 1) {
System.out.println("transfer disk " + n + " from " + src + " to " + dest);
return;
}
//transfer top n-1 from src to helper using dest as 'helper'
towerOfHanoi(n - 1, src, dest, helper);
//transfer nth from src to dest
System.out.println("transfer disk " + n + " from " + src + " to " + helper);
//transfer n-1 from helper to dest using src as 'helper'
towerOfHanoi(n - 1, helper, src, dest);
}
public static void main(String args[]) {
int n = 4;
towerOfHanoi(n, "A", "B", "C");
}
}
//50. Pow(x, n)
class Solution {
public double myPow(double x, int n) {
long power = n; // handle Integer.MIN_VALUE
if (power < 0) {
x = 1 / x;
power = -power;
}
double result = 1.0;
while (power > 0) {
if ((power & 1) == 1) { // if power is odd
result *= x;
}
x *= x;
power >>= 1; // power = power / 2
}
return result;
}
}