Learning DP. Awsome example. Thanks!
Anonymous - Feb 3, 2015
Learning DP. Awsome example. Thanks!
Thank you :)
Maximum continuous sum subarray problem
Problem You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum.
EXAMPLE
Input: {2, -8, 3, -2, 4, -10}
Output: 5 (i.e., {3, -2, 4})
Solution Method 1 - Brute force
The outer loop picks the beginning element, the inner loop finds the maximum possible sum with first element picked by outer loop and compares this maximum with the overall maximum.
[Read More]
Find the First Duplicated Integer in an Array containing numbers from 1 to N Without Using Extra Memory
let the array be 3 1 2 1 3 4 first repeated integ… Unknown - Mar 6, 2013let the array be 3 1 2 1 3 4
first repeated integer is 3 here
start from the first and go till the end
add n+1 to the a[a[i]] where i is the current index.
iterate again dividing the values by n+1 if values comes 1 . the remainder is the repeated one.
[Read More]
Find the First Duplicated Integer in an Array containing numbers from 1 to N Without Using Extra Memory
Question: There is a size-N array of integers whose values range from 1 to N. Some integers are duplicated. Find the first duplicate and its index without using any extra memory (not even O(1)).
Solution There are a few keys in the question that we should consider:
The array size is a finite number N which is also the upper limit for any integer inside the array. Hence, if the array size is 10, then there are ten elements in the array and each of those elements is between 1 and 10.
[Read More]
Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .
for(int j=arrIndex/2 ; j < arrIndex;j++) …
shanky - Nov 0, 2014
for(int j=arrIndex/2 ; j < arrIndex;j++)
{
if(array[j]==1)
return j;//this is our index
}
This makes the approach O(n)
Do a regular binary search after finding the cap , with range i/2 to i
Hi Shanky, you are right. That’s what I have done :)
Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .
Approach 1(bad): Iterating over the array until we find 1, as the array is sort. In worst case it will go till the last element, and hence this is bad approach.
Approach 2 : Club binary search approach and array’s random access property
Since the array is infinitely increasing i.e. we don’t know array size in advance, so we can’t directly apply traditional BinarySearch (in which we partition the problem size in half in each iteration, kind of top down approach).
[Read More]
Given an array of n integers from 1 to n with one integer repeated twice
Problem - Given an array of n integers from 1 to n with one integer repeated twice
This can be done via normal array traversal or hash table to find duplicates. But since we are given that the integers are from 1 to n, then there are better methods available.
Approach 1 - Arithmetic sum approach
So, the efficient method to solve it calculate the sum of actual input array, and expected sum of the array.
[Read More]