Sundeep
BAN USERpublic static void PrintIncreasingSubArray(int[] iarInput)
{
int iTmpStart = 0; // Temp. Start Index.
int iTmpLength = 0; // Temp. Length.
int iResStart = 0; // Result Start Index.
int iResLength = 0; // Result Length.
// Loop from index 1 to the end of list.
for(int iIndex=1; iIndex < iarInput.length; iIndex++)
{
// Check if the sequence is increasing/decreasing-flat.
if(iarInput[iIndex] <= iarInput[iIndex-1])
{
// Flat or decreasing trend.
iTmpStart = iIndex;
iTmpLength = 0;
}else{
// Increasing Trend.
iTmpLength++;
// As the new found sequence is bigger, update the old result values.
if(iTmpLength > iResLength)
{
iResStart = iTmpStart;
iResLength = iTmpLength;
}
}
}
// Print the longest increasing sub-array using start index and length of result.
for(int iCount = 0; iCount <= iResLength; iCount++)
{
System.out.print(iarInput[iResStart + iCount]);
System.out.print(", ");
}
}
I'm not able to get hang on need for an algorithm with complexity > O(n).
I'm thinking of the below algorithm. Let me know if I missed something in the question.
1. Loop from i = 1 to length
2. In each iteration, if Array[i] <= Array[i -1]
2.a. Set the start index of result to i;
2.b else: Increment the temp. size counter.
2.b: If the result size < temp size counter, update the result start index and the result size.
3. Iterate through result start index for result size and print the numbers from the given array.
Time complexity is O(n) and its in-place algorithm.
Just to understand the question,
if the input is {1,5,7,8,9,45,78,2,4,1,7,12,23,34,6,23,45};
The increasing sub-arrays are
{1,5,7,8,9,45,78} -> Longest and should be the result.
{2,4}
{1,7,12,23,34}
{6,23,45}
The output should be {1, 5, 7, 8, 9, 45, 78}
Can someone confirm?
Looks to be working on first look. But after thinking about it a bit, I guess there seems to be a mistake.
1. Lets say, The person assumes up/down times as 25/10 instead of the actual 20/15 mins.
2. He Notes the time as 10:00 and starts uphill. Actual time taken is 20mins but he assumes it took 25mins. On reaching he sets the Top clock to 10:25. The Bot clock reads 10:20.
3. He starts downhill and it actually takes 15mins but he assumes it as 10mins. On reaching Bot Clock he finds it to be 10:35 just as expected. The Top Clock should show 10:25+15 = 10:40.
At this point, He may assume that the Top Clock should be 10:25 + 10 = 10:35mins, but its 10:40.
3. Now here's the catch in your solution.
He notes the Bot Clock value as 10:35 and goes up hill which actually takes 20mins.
Now he expects the Top Clock to show 10:35(Bot Reference) + 25mins(assumed uphill time) = 11:00.
The actual Top Clock value will be 10:40(actual value before start of uphill) + 20mins(actual uphil time) = 11:00.
Both his expectation and actual value match which is 11:00, but the actual time shown by the Bot Clock will be 10:35 + 20mins = 10:55.
Not sure how he actually sees 11:05.
Please check and let me know if I missed something.
Otherwise, good thought process.
Some first thoughts.
It can be done with an approach similar to binary search.
1. For the sake of simplicity, start with i = N/(2.0f). This can be further optimized as higher numbers have roots which are much less than the half of it, so the division by 2.0f in this algorithm can be optimized.
2. Do a float comparison between i*i with N.
2.1) If the product exceeds, substitute i with i/(2.0f). Loop further.
2.2) If the product is less, substitute i with i + i/(2.0f). Loop further.
2.3) If the product is within a reasonable tolerance to the given input, N. i is the result.
If a quick result is required, tolerance should be more. If a very precise result is required, tolerance should be less and this demands more number of iterations.
Usage: getCountsfast(12345,'2');
- Sundeep July 15, 2016