8000 finish CountTripletsGeometricProgression, MinCostPath · jacobklo/jalgorithmCPP@0c76732 · GitHub
[go: up one dir, main page]
Skip to content

Commit 0c76732

Browse files
jacobklojacobklo
committed
finish CountTripletsGeometricProgression, MinCostPath
1 parent 7832156 commit 0c76732

File tree

8 files changed

+226
-6
lines changed

8 files changed

+226
-6
lines changed

‎README.md

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,14 @@ unlike normal projects.
3636
* [Singleton](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/DesignPattern/Singleton.h)
3737
***
3838

39+
#### Dictionary
40+
* [Count Triplets In Geometric Progression](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Dictionary/CountTripletsGeometricProgression.h)
41+
***
42+
43+
#### Dynamic Programming
44+
* [Min Cost Path in Matrix](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/DynamicProgramming/MinCostPath.h)
45+
***
46+
3947
#### Math
4048
* [BusStop - Hackerrank](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Math/BusStop.h)
4149
* [SqureRoot](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Math/SquareRoot.h)

‎src/CMakeLists.txt

Lines changed: 2 additions & 0 deletions
< 8000 td data-grid-cell-id="diff-148715d6ea0c0ea0a346af3f6bd610d010d490eca35ac6a9b408748f7ca9e3f4-37-38-2" data-line-anchor="diff-148715d6ea0c0ea0a346af3f6bd610d010d490eca35ac6a9b408748f7ca9e3f4R38" data-selected="false" role="gridcell" style="background-color:var(--diffBlob-additionLine-bgColor, var(--diffBlob-addition-bgColor-line));padding-right:24px" tabindex="-1" valign="top" class="focusable-grid-cell diff-text-cell right-side-diff-cell left-side">+
Dictionary/CountTripletsGeometricProgression.h
Original file line numberDiff line numberDiff line change
@@ -35,5 +35,7 @@ add_executable(jalgorithmCPP
3535
DesignPattern/Singleton.h
3636
Array/MinSwap.h
3737
DynamicProgramming/Abbreviation.h
38
39+
DynamicProgramming/MinCostPath.h
3840
)
3941

‎src/Dictionary/CountTripletsGeometricProgression.h

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
//
2+
// Created by Jacob Lo on 10/9/18.
3+
//
4+
5+
/*
6+
* MEDIUM
7+
* Find all triplets in a sorted array that forms Geometric Progression
8+
* https://www.geeksforgeeks.org/find-all-triplets-in-a-sorted-array-that-forms-geometric-progression/
9+
* https://www.hackerrank.com/challenges/count-triplets-1/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps
10+
*
11+
* Calculate all triplets in an array that is in geometric progression form and i<j<k
12+
* More in the end
13+
*/
14+
#pragma once
15+
16+
#include <vector>
17+
#include <map>
18+
19+
using namespace std;
20+
21+
namespace CountTripletsGeometricProgression {
22+
23+
long countTriplets(const vector<long>& arr, long r) {
24+
25+
/// create a map, with key is r progression, value is vector of positions occurance
26+
long currentProgression = 1;
27+
map<long, long> cmap;
28+
29+
for ( int i = 0 ; i < arr.size() ; i++ ) {
30+
31+
// making sure map has all progression keys
32+
while ( arr[i] >= currentProgression ) {
33+
cmap[currentProgression] = 0;
34+
currentProgression *= r;
35+
}
36+
37+
if ( cmap.find(arr[i]) != cmap.end() ) {
38+ cmap[arr[i]]++;
39+
}
40+
}
41+
/// loop through map, count each triplets
42+
int result = 0;
43+
for ( map<long, long>::iterator it = cmap.begin() ; it != cmap.end() ; ++it ) {
44+
45+
map<long, long>::iterator current = it;
46+
long currentResult = current->second;
47+
for ( int j = 0 ; j < 2; j++ ) {
48+
++current;
49+
if ( current == cmap.end() ) {
50+
return result;
51+
}
52+
currentResult *= current->second;
53+
}
54+
result += currentResult;
55+
}
56+
return result;
57+
}
58+
}
59+
60+
/*
61+
* You are given an array and you need to find number of tripets of indices such that the elements at those indices are in geometric progression for a given common ratio and .
62+
For example, . If , we have and at indices and .
63+
Function Description
64+
Complete the countTriplets function in the editor below. It should return the number of triplets forming a geometric progression for a given as an integer.
65+
countTriplets has the following parameter(s):
66+
arr: an array of integers
67+
r: an integer, the common ratio
68+
Input Format
69+
The first line contains two space-separated integers and , the size of and the common ratio.
70+
The next line contains space-seperated integers .
71+
Constraints
72+
73+
74+
75+
Output Format
76+
Return the count of triplets that form a geometric progression.
77+
Sample Input 0
78+
4 2
79+
1 2 2 4
80+
Sample Output 0
81+
2
82+
Explanation 0
83+
There are triplets in satisfying our criteria, whose indices are and
84+
Sample Input 1
85+
6 3
86+
1 3 9 9 27 81
87+
Sample Output 1
88+
6
89+
Explanation 1
90+
The triplets satisfying are index , , , , and .
91+
Sample Input 2
92+
5 5
93+
1 5 5 25 125
94+
Sample Output 2
95+
4
96+
Explanation 2
97+
The triplets satisfying are index , , , .
98+
*/

‎src/DynamicProgramming/MinCostPath.h

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
//
2+
// Created by Jacob Lo on 10/10/18.
3+
//
4+
5+
/*
6+
* MEDIUM
7+
* Min Cost Path
8+
* https://www.geeksforgeeks.org/min-cost-path-dp-6/
9+
*
10+
* For a matrix, find the minimum path from 1 node to the end. from start(0,0), we can only go left or lower
11+
*/
12+
#pragma once
13+
14+
#include <vector>
15+
16+
using namespace std;
17+
18+
namespace MinCostPath {
19+
20+
int minCostPath( const vector< vector<int> >& map) {
21+
22+
/// construct a 2D array, storing the min cost from start (0,0) to (i,j). load the first column and row
23+
vector< vector< int> > cmap( map.size(), vector<int>( map[0].size(), 0 ));
24+
cmap[0][0] = map[0][0];
25+
for ( int i = 1 ; i < map.size() ; i++ ) {
26+
cmap[i][0] = map[i][0] + cmap[i-1][0];
27+
}
28+
for ( int i = 1 ; i < map[0].size() ; i++ ) {
29+
cmap[0][i] = map[0][i] + cmap[0][i-1];
30+
}
31+
32+
/// for loop, (i,j) position, we will calculate from top or left to (i,j) is minimum
33+
for ( int i = 1 ; i < cmap.size() ; i++ ) {
34+
for (int j = 1; j < cmap[i].size(); j++) {
35+
36+
/// Case 1: from top
37+
int top = cmap[i-1][j];
38+
39+
/// Case 2: from left
40+
int left = cmap[i][j-1];
41+
42+
/// update (i,j) min cost
43+
cmap[i][j] = ( top > left ? left : top ) + map[i][j];
44+
}
45+
}
46+
47+
return cmap[cmap.size()-1][cmap[0].size()-1];
48+
}
49+
}
50+
51+
/*
52+
* Min Cost Path | DP-6
53+
Given a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0). Each cell of the matrix represents a cost to traverse through that cell. Total cost of a path to reach (m, n) is sum of all the costs on that path (including both source and destination). You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1) and (i+1, j+1) can be traversed. You may assume that all costs are positive integers.
54+
55+
For example, in the following figure, what is the minimum cost path to (2, 2)?
56+
57+
58+
The path with minimum cost is highlighted in the following figure. The path is (0, 0) –> (0, 1) –> (1, 2) –> (2, 2). The cost of the path is 8 (1 + 2 + 2 + 3).
59+
60+
61+
Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.
62+
63+
64+
65+
1) Optimal Substructure
66+
The path to reach (m, n) must be through one of the 3 cells: (m-1, n-1) or (m-1, n) or (m, n-1). So minimum cost to reach (m, n) can be written as “minimum of the 3 cells plus cost[m][n]”.
67+
68+
minCost(m, n) = min (minCost(m-1, n-1), minCost(m-1, n), minCost(m, n-1)) + cost[m][n]
69+
70+
2) Overlapping Subproblems
71+
Following is simple recursive implementation of the MCP (Minimum Cost Path) problem. The implementation simply follows the recursive structure mentioned above.
72+
*/

‎src/main.cpp

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -8,14 +8,13 @@
88

99
#include "String/ContainersToString.h"
1010

11-
#include "Array/MinSwap.h"
11+
#include "Dictionary/CountTripletsGeometricProgression.h"
1212

1313
using namespace std;
1414

1515

1616
int main() {
17-
// vector<int> arr{ 8,7,6,5,4,3,2,1 };
18-
vector<int> arr{ 4,3,1,2};
19-
int result = MinSwap::minimumSwaps( arr) ;
17+
18+
2019
cout << result;
2120
}

‎test/CMakeLists.txt

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -40,8 +40,11 @@ add_executable(jalgorithmCPP_Test
4040
../src/DataStructure/Deque.h
4141
Sort/QuickSortTest.cpp
4242
../src/Sort/QuickSort.h
43-
../src/String/ContainersToString.h
4443
Search/BinarySearchTest.cpp
4544
../src/Search/BinarySearch.h
46-
../src/DesignPattern/Singleton.h)
45+
Dictionary/CountTripletsGeometricProgressionTest.cpp
46+
../src/Dictionary/CountTripletsGeometricProgression.h
47+
DynamicProgramming/MinCostPathTest.cpp
48+
../src/DynamicProgramming/MinCostPath.h
49+
../src/String/ContainersToString.h)
4750

‎test/Dictionary/CountTripletsGeometricProgressionTest.cpp

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
//
2+
// Created by Jacob Lo on 10/10/18.
3+
//
4+
5+
#include "catch.hpp"
6+
#include "Dictionary/CountTripletsGeometricProgression.h"
7+
8+
using namespace CountTripletsGeometricProgression;
9+
10+
TEST_CASE("Test Count Triplets in Geometric Progression", "[TestCountTripletsGeometricProgression]") {
11+
vector<long> arr{ 1,3,3,9,9};
12+
long result = CountTripletsGeometricProgression::countTriplets( arr, 3 );
13+
REQUIRE ( 4 == result );
14+
}

‎test/DynamicProgramming/MinCostPathTest.cpp

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
//
2+
// Created by Jacob Lo on 10/10/18.
3+
//
4+
5+
#include "catch.hpp"
6+
#include "DynamicProgramming/MinCostPath.h"
7+
8+
using namespace MinCostPath;
9+
10+
TEST_CASE("Test Min Cost Path", "[TestMinCostPath]") {
11+
vector< vector<int> > map { { 1,3,1,1 },
12+
{ 2,4,4,2 },
13+
{ 3,1,1,3 },
14+
{ 3,1,1,1 }};
15+
int result = MinCostPath::minCostPath( map );
16+
REQUIRE( 10 == result);
17+
}
18+
19+
TEST_CASE("Test Min Cost Path2", "[TestMinCostPath2]") {
20+
vector< vector<int> > map { {1,2},
21+
{1,1}};
22+
int result = MinCostPath::minCostPath( map );
23+
REQUIRE( 3 == result);
24+
}

0 commit comments

Comments
 (0)
0