Skip to content

Instantly share code, notes, and snippets.

@matthewjberger
Last active October 4, 2016 19:20
Show Gist options
  • Save matthewjberger/6a1c81b03785a1d5e79b6d2faa6165d7 to your computer and use it in GitHub Desktop.
Save matthewjberger/6a1c81b03785a1d5e79b6d2faa6165d7 to your computer and use it in GitHub Desktop.
#include <iostream>
#include "gtest/gtest.h"
int GetPositionOfMaxInteger(int* arr, int start, int end);
void RearrangeArray(int* arr, int size);
int main(int argc, char** argv)
{
testing::InitGoogleTest(&argc, argv);
RUN_ALL_TESTS();
std::getchar();
}
int GetPositionOfMaxInteger(int* arr, int start, int end)
{
if (start == end) return start;
// Split array in two and find the maximum number's position on on each side
int midpoint = floor(((end - start) / 2.0) + 0.5);
int maxPosLeft = GetPositionOfMaxInteger(arr, start, start + midpoint - 1);
int maxPosRight = GetPositionOfMaxInteger(arr, start + midpoint, end);
return (arr[maxPosLeft] >= arr[maxPosRight]) ? maxPosLeft : maxPosRight;
}
void RearrangeArray(int* arr, int size)
{
int firstPositivePosition, currentIndex;
for(currentIndex = 0, firstPositivePosition = -1; currentIndex < size; currentIndex++)
{
if(arr[currentIndex] < 0)
{
int tmp = arr[++firstPositivePosition];
arr[firstPositivePosition] = arr[currentIndex];
arr[currentIndex] = tmp;
}
}
}
/* Unit Tests */
TEST(CanGetPositionOfMaxInteger, SingleLargestValue)
{
int arr0[] = { 3, 1, 5, 6 };
int pos0 = GetPositionOfMaxInteger(arr0, 0, 3);
ASSERT_EQ(pos0, 3);
int arr1[] = { 3, 6 };
int pos1 = GetPositionOfMaxInteger(arr1, 0, 1);
ASSERT_EQ(pos1, 1);
int arr[] = { 3, 6, 9, 1, 240, 3, -1 };
int pos = GetPositionOfMaxInteger(arr, 0, 6);
ASSERT_EQ(pos, 4);
}
TEST(CanGetPositionOfMaxInteger, MultipleLargestValues)
{
int arr[] = { 3, 24, 9, 1, 24, 24, 3, -1 };
int pos = GetPositionOfMaxInteger(arr, 0, 8);
ASSERT_EQ(pos, 1);
}
TEST(CanGetPositionOfMaxInteger, RequestedSet)
{
int arr[] = { 1, 4, 9, 3, 4, 9, 5, 6, 9, 3, 7 };
int pos = GetPositionOfMaxInteger(arr, 0, 8);
ASSERT_EQ(pos, 2);
}
TEST(CanRearrangeArray, NegativeBeforePositiveRequestedSet)
{
int arr[] = { 4, -3, 9, 8, 7, -4, -2, -1, 0, 6, -5 };
int size = 11;
RearrangeArray(arr, size);
bool foundPositive = false;
bool correct = true;
for (int i = 0; i < size; i++)
{
bool negative = false;
if (arr[i] < 0) negative = true;
if (arr[i] >= 0) foundPositive = true;
if (negative && foundPositive)
{
correct = false;
break;
};
}
ASSERT_TRUE(correct);
}
#include <iostream>
int GetPositionOfMaxInteger(int* arr, int start, int end)
{
if (start == end) return start;
int midpoint = floor(((start + end) / 2.0) + 0.5);
int maxPosLeft = GetPositionOfMaxInteger(arr, start, midpoint - 1);
int maxPosRight = GetPositionOfMaxInteger(arr, midpoint, end);
return (arr[maxPosLeft] >= arr[maxPosRight]) ? maxPosLeft : maxPosRight;
}
void RearrangeArray(int* arr, int size)
{
int firstPositivePosition, currentIndex;
for (currentIndex = 0, firstPositivePosition = -1; currentIndex < size; currentIndex++)
{
if (arr[currentIndex] < 0)
{
int tmp = arr[++firstPositivePosition];
arr[firstPositivePosition] = arr[currentIndex];
arr[currentIndex] = tmp;
}
}
}
int main(int argc, char** argv)
{
int arr[] = { 1, 4, 9, 3, 4, 9, 5, 6, 9, 3, 7 };
int size = 10;
int pos = GetPositionOfMaxInteger(arr, 0, size);
std::cout << "First array: ";
for(int i = 0; i < size; i++)
{
std::cout << arr[i];
if (i < size - 1) std::cout << ",";
else std::cout << std::endl;
}
std::cout << "Position of Leftmost Largest Integer: " << pos << std::endl;
int arr2[] = { 4, -3, 9, 8, 7, -4, -2, -1, 0, 6, -5 };
size = 11;
std::cout << "Second array: ";
for(int i = 0; i < size; i++)
{
std::cout << arr2[i];
if (i < size - 1) std::cout << ",";
else std::cout << std::endl;
}
RearrangeArray(arr2, size);
std::cout << "Negative values moved to beginning of array: ";
for(int i = 0; i < size; i++)
{
std::cout << arr2[i];
if (i < size - 1) std::cout << ",";
else std::cout << std::endl;
}
std::getchar();
}
#include <iostream>
int CountOfNumbersInRange(int* arr, int min, int max, int size)
{
int count = 0;
for(int i = 0; i < size; i++)
if ((min <= arr[i]) && (arr[i] <= max)) count++;
return count;
}
int main(int argc, char** argv)
{
int arr[] = { 5, 6, 9, 4, 4, 2, 2, 9, 5, 3, 4, 0, 1, 8, 5, 3, 8, 7 };
int size = 18;
int min = 2;
int max = 7;
int output = CountOfNumbersInRange(arr, min, max, size);
std::cout << "Input: ";
for(int i = 0; i < size; i++)
{
std::cout << arr[i];
if (i < size - 1) std::cout << ",";
else std::cout << std::endl;
}
std::cout << "Numbers between range " << min << " and " << max << ": " << output << std::endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment