8000 finish Larry's Array in Hackerrank · jacobklo/jalgorithmCPP@e056f84 · GitHub
[go: up one dir, main page]
Skip to content

Commit e056f84

Browse files
jacobklojacobklo
committed
finish Larry's Array in Hackerrank
1 parent 15de4dc commit e056f84

File tree

5 files changed

+98
-0
lines changed

5 files changed

+98
-0
lines changed

‎README.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,10 @@ unlike normal projects.
2020

2121
## List of Algorithm curently have:
2222

23+
#### Array
24+
* [Larry's Array - Hackerrank](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Array/LarrysArray.h)
25+
* [MinSwap](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Array/MinSwap.h)
26+
***
2327
#### Backtrack
2428
* [MostEleganceString - Hackerrank](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Backtrack/MostEleganceString.h)
2529
* [Davis' Staircase - Hackerrank](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Backtrack/DavisStaircase.h)

‎src/Array/LarrysArray.h

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
//
2+
// Created by Jacob Lo on 11/4/18.
3+
//
4+
5+
/*
6+
* MEDIUM
7+
* https://www.hackerrank.com/challenges/larrys-array/problem
8+
*
9+
* Larry has been given a permutation of a sequence of natural numbers incrementing from as an array. He must determine whether the array can be sorted using the following operation any number of times:
10+
Choose any consecutive indices and rotate their elements in such a way that .
11+
For example, if :
12+
A rotate
13+
[1,6,5,2,4,3] [6,5,2]
14+
[1,5,2,6,4,3] [5,2,6]
15+
[1,2,6,5,4,3] [5,4,3]
16+
[1,2,6,3,5,4] [6,3,5]
17+
[1,2,3,5,6,4] [5,6,4]
18+
[1,2,3,4,5,6]
19+
20+
YES
21+
*/
22+
#pragma once
23+
24+
#include <vector>
25+
26+
using namespace std;
27+
28+
namespace LarrysArray {
29+
void rotateClockwise( vector<int>& arr, int startPos) {
30+
int tmp = arr[ startPos ];
31+
arr[ startPos ] = arr[ startPos + 1 ];
32+
arr[ startPos + 1 ] = arr[ startPos + 2 ];
33+
arr[ startPos + 2 ] = tmp;
34+
}
35+
36+
bool larrysArray( vector<int> arr ) {
37+
38+
/// for loop
39+
for ( int i = 0 ; i < arr.size() ; i++ ) {
40+
/// for loop to end to find next smallest element
41+
int currentSmallestPos = i;
42+
int currentSmallest = arr[i];
43+
for (int j = i+1; j < arr.size(); j++) {
44+
if (currentSmallest > arr[j]) {
45+
currentSmallestPos = j;
46+
currentSmallest = arr[j];
47+
}
48+
}
49+
50+
/// do rotate and check element in right position, return false if cannot
51+
while (currentSmallestPos > i) {
52+
// default, currentSmallestPos is at last pos of the 3 elements
53+
int swapIndex = currentSmallestPos - 2;
54+
// if currentSmallestPos is in the middle of 3 elements
55+
if ( currentSmallestPos - 1 == i) {
56+
swapIndex = currentSmallestPos - 1;
57+
}
58+
// special case, overflow protection, if currentSmallestPos is last element of whole array
59+
if ( currentSmallestPos == arr.size() - 1) {
60+
swapIndex = currentSmallestPos - 2;
61+
}
62+
rotateClockwise( arr, swapIndex);
63+
currentSmallestPos--;
64+
}
65+
}
66+
/// check if last 3 is sorted
67+
return arr[ arr.size() - 3] < arr[ arr.size() - 2] &&
68+
arr[ arr.size() - 2] < arr[ arr.size() - 1];
69+
}
70+
}

‎src/CMakeLists.txt

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,5 +43,7 @@ add_executable(jalgorithmCPP
4343
DataStructure/QueueUsingTwoStack.h
4444
Search/TripleSum.h
4545
Backtrack/AddTwoNumbers.h
46+
DynamicProgramming/Candies.h
47+
Array/LarrysArray.h
4648
)
4749

‎test/Array/LarrysArrayTest.cpp

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
//
2+
// Created by Jacob Lo on 11/4/18.
3+
//
4+
5+
#include "catch.hpp"
6+
#include "Array/LarrysArray.h"
7+
8+
TEST_CASE( "Most Larry's Array", "[LarrysArrayTest1]" ) {
9+
vector<int> arr{ 1,6,5,2,4,3 };
10+
vector<int> arr2{ 1,2,3,5,4 };
11+
vector<int> arr3{ 3,1,2 };
12+
bool result = LarrysArray::larrysArray( arr );
13+
bool result2 = LarrysArray::larrysArray( arr2 );
14+
bool result3 = LarrysArray::larrysArray( arr3 );
15+
REQUIRE( result == true );
16+
REQUIRE( result2 == false );
17+
REQUIRE( result3 == true );
18+
}

‎test/CMakeLists.txt

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -54,6 +54,10 @@ add_executable(jalgorithmCPP_Test
5454
../src/Backtrack/DavisStaircase.h
5555
Backtrack/AddTwoNumbersTest.cpp
5656
../src/Backtrack/AddTwoNumbers.h
57+
Array/LarrysArrayTest.cpp
58+
../src/Array/LarrysArray.h
59+
DynamicProgramming/CandiesTest.cpp
60+
../src/DynamicProgramming/Candies.h
5761
../src/String/ContainersToString.h
5862
)
5963

0 commit comments

Comments
 (0)
0