FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java2/DynamicProgramming/CoinChange.java at master · Tarun27/Java2 · GitHub
Tarun27
/
Java2
Public
forked from
TheAlgorithms/Java
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Java2
/
DynamicProgramming
/
CoinChange.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
79 lines (66 loc) · 2.63 KB
Breadcrumbs
Java2
/
DynamicProgramming
/
CoinChange.java
Copy path
File metadata and controls
79 lines (66 loc) · 2.63 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
package
DynamicProgramming
;
/**
* @author Varun Upadhyay (https://github.com/varunu28)
*/
public
class
CoinChange
{
// Driver Program
public
static
void
main
(
String
[]
args
) {
int
amount
=
12
;
int
[]
coins
= {
2
,
4
,
5
};
System
.
out
.
println
(
"Number of combinations of getting change for "
+
amount
+
" is: "
+
change
(
coins
,
amount
));
System
.
out
.
println
(
"Minimum number of coins required for amount :"
+
amount
+
" is: "
+
minimumCoins
(
coins
,
amount
));
}
/**
* This method finds the number of combinations of getting change for a given amount and change coins
*
* @param coins The list of coins
* @param amount The amount for which we need to find the change
* Finds the number of combinations of change
**/
public
static
int
change
(
int
[]
coins
,
int
amount
) {
int
[]
combinations
=
new
int
[
amount
+
1
];
combinations
[
0
] =
1
;
for
(
int
coin
:
coins
) {
for
(
int
i
=
coin
;
i
<
amount
+
1
;
i
++) {
combinations
[
i
] +=
combinations
[
i
-
coin
];
}
// Uncomment the below line to see the state of combinations for each coin
// printAmount(combinations);
}
return
combinations
[
amount
];
}
/**
* This method finds the minimum number of coins needed for a given amount.
*
* @param coins The list of coins
* @param amount The amount for which we need to find the minimum number of coins.
* Finds the the minimum number of coins that make a given value.
**/
public
static
int
minimumCoins
(
int
[]
coins
,
int
amount
) {
//minimumCoins[i] will store the minimum coins needed for amount i
int
[]
minimumCoins
=
new
int
[
amount
+
1
];
minimumCoins
[
0
] =
0
;
for
(
int
i
=
1
;
i
<=
amount
;
i
++) {
minimumCoins
[
i
] =
Integer
.
MAX_VALUE
;
}
for
(
int
i
=
1
;
i
<=
amount
;
i
++) {
for
(
int
coin
:
coins
) {
if
(
coin
<=
i
) {
int
sub_res
=
minimumCoins
[
i
-
coin
];
if
(
sub_res
!=
Integer
.
MAX_VALUE
&&
sub_res
+
1
<
minimumCoins
[
i
])
minimumCoins
[
i
] =
sub_res
+
1
;
}
}
}
// Uncomment the below line to see the state of combinations for each coin
//printAmount(minimumCoins);
return
minimumCoins
[
amount
];
}
// A basic print method which prints all the contents of the array
public
static
void
printAmount
(
int
[]
arr
) {
for
(
int
i
=
0
;
i
<
arr
.
length
;
i
++) {
System
.
out
.
print
(
arr
[
i
] +
" "
);
}
System
.
out
.
println
();
}
}
Back
|
FazBrowse Home
|
New Git URL