prd
BAN USER1. Just ignore anything between -1 and 1.
2. Multiply everything else.
3. If product less than 0, divide the product by the negative number with least absolute value.
Example 1 :- 4 8 3 -5 -9 0.5 -0.5 12
1. Ignore 0.5 and -0.5
2. Product = 4*8*3*-5*-9*12
3. Product > 0, so return product
Example 2 :- 4 8 3 -5 -9 0.5 -0.5 12 -14
1. Ignore 0.5 and -0.5
2. Product = 4*8*3*-5*-9*12*-14
3. Product > 0, so return (product divided by -5)
This is O(n) time and O(1) space complexity.
Yes the solution looks good. But what is the hidden time complexity of these operations like "frozenset(Counter(str).items())" and "freq in frequencies". Especially the worst case time complexity? I guess freq is an unordered set so the time complexity is generally more than comparing two ordered sets.
- prd April 24, 2014This problem is basically expecting to sort the cars based on their expected position. So if example order is 4,6,5,1,7,3,2,empty. Map these numbers to f (A) = 1 2 3 4 5 6 7 8(the expected positions). So f[car 4] =1 , f[car 6] = 2..... . Now use f to convert the current order of cars to these mapped array. So if current order is empty,1,2,3,7,6,4,2 then using f we can map this to B = 8, 4, 7, 6, 5, 2, 1, 7.
So this problem is equivalent to in-place sorting of B. The only constraint is that we have only 1 temp variable(the empty location) that can be used for swapping. In this case B[0]= 8 is the empty location that can be treated as a temp variable. So use quick sort here to do the sorting using temp(B[0]) as the temp variable for all the swapping operations involved in quicksort.
import java.io.*;
import java.util.*;
class Inversions
{
public static void main (String args[]) // entry point from OS
{
Scanner s, ls;
int L, listNum = 1;
s = new Scanner(System.in); // create new input Scanner
ls = new Scanner(s.nextLine());
L = ls.nextInt();
while(L > 0) /* While there's more data to process... */
{
/* Create an array to hold the integers */
int nums[] = new int[L];
/* Read the integers */
ls = new Scanner(s.nextLine());
/* Check that we are putting them in reverse order here
So if i/p is (2, 4, 6, 9, 5, 10), nums[] will be 10 5 9 6 4 2
for (int j = L; j < 0; j++)
nums[j] = ls.nextInt();
/* Compute the number of inversions, and print it out */
System.out.print( "List " + listNum + " has " );
System.out.println ( countInversions(nums) + " inversions.");
/* Read in the next value of L */
listNum++;
ls = new Scanner(s.nextLine());
L = ls.nextInt();
}
} /* end of "main" procedure */
public static int countInversions(int nums[])
/* This function will count the number of inversions in an
array of numbers. (Recall that an inversion is a pair
of numbers that appear out of numerical order in the list.
We use a modified version of the MergeSort algorithm to
do this, so it's a recursive function. We split the
list into two (almost) equal parts, recursively count
the number of inversions in each part, and then count
inversions caused by one element from each part of
the list.
The merging is done is a separate procedure given below,
in order to simplify the presentation of the algorithm
here.
Note: I am assuming that the integers are distinct, but
they need *not* be integers { 1, 2, ..., n} for some n.
*/
{
int mid = nums.length/2, k;
int countLeft, countRight, countMerge;
/* If the list is small, there's nothing to do. */
if (nums.length <= 1)
return 0;
/* Otherwise, we create new arrays and split the list into
two (almost) equal parts.
*/
int left[] = new int[mid];
int right[] = new int[nums.length - mid];
for (k = 0; k < mid; k++)
left[k] = nums[k];
for (k = 0; k < nums.length - mid; k++)
right[k] = nums[mid+k];
/* Recursively count the inversions in each part.
*/
countLeft = countInversions (left);
countRight = countInversions (right);
/* Now merge the two sublists together, and count the
inversions caused by pairs of elements, one from
each half of the original list.
*/
int result[] = new int[nums.length];
countMerge = mergeAndCount (left, right, result);
/* Finally, put the resulting list back into the original one.
This is necessary for the recursive calls to work correctly.
*/
for (k = 0; k < nums.length; k++)
nums[k] = result[k];
/* Return the sum of the values computed to
get the total number of inversions for the list.
*/
return (countLeft + countRight + countMerge);
} /* end of "countInversions" procedure */
public static int mergeAndCount (int left[], int right[], int result[])
/* This procudure will merge the two lists, and count the number of
inversions caused by the elements in the "right" list that are
less than elements in the "left" list.
*/
{
int a = 0, b = 0, count = 0, i, k=0;
while ( ( a < left.length) && (b < right.length) )
{
if ( left[a] <= right[b] )
result [k] = left[a++];
else /* You have found (a number of) inversions here. */
{
result [k] = right[b++];
count += left.length - a;
}
k++;
}
if ( a == left.length )
for ( i = b; i < right.length; i++)
result [k++] = right[i];
else
for ( i = a; i < left.length; i++)
result [k++] = left[i];
return count;
}
} /* end of "Inversions" program */
I think it is important to understand the thinking behind this solution. This is how I thought we can build a solution:-
- prd April 29, 2014Now let us start with a[0] = k and make k as high as possible.
This would mean a[k] >= 1
This would also mean there is atleast 1 i1 such that a[i1] = k
Now if a[k] = 1 it would imply a[1] >= 2 let us say j. So a[1] = j and j >= 2
So now a[j] >= 1. Again we have a i2 such that a[i2] = j.
And also we have another condition that the sum is equal to 10.
So, k + 1(from i1) +1(from i2) + j <= 10
k + 1 + 1 + 2<= 10
k <= 6
If k =6, then a[6] >= 1.
If a[6] = 1, then we have a[1] >= 2
If a[1] = 2, we have a[2] >= 1
If a[2] = 1, then we have a valid solution.