SecretAgent
BAN USERrecheck your code with one more entry say value: 4, Index: 6
- SecretAgent March 20, 2012@Chen your algo looks good.. but the first step can be achieved in log(n) time right (a binary search can be done)?
Then the algo would take O(log(n)) + O(n) instead of O(n) + O(n)..
For understanding the solution better i'll the algorithm in two passes at max (still order is O(n)):
In the first pass find out the maximum and minimum elements. If the index of maximum is greater than that of minimum then the problem is solved. Otherwise find:
let min,max be the found minimum and maximum elements respectively.
maximum(diff(minium element that is left to max,max),diff(min,maximum element that is right to min))
If we manage the variables properly we can do it in one pass :)
Eg: 5, 15, 2, 10, 20, 1, 17, 0, 8, 16
Apparently the required indexes are 2,4 (max difference =18)
Now using algo,
minimum element = 0
maximum element = 20
but index of 0 > index of 20
now minimum element left of 20 is 2, difference1 = 18
maximum element right of 0 is 16, difference2 = 16
maximum(difference1, difference2) = 18
Order is O(n) and if we manage variables properly, we can do it in one pass
It is grouping P1,P3 and P2,p4 right not swapping
after rearragement it should look like p1,p3,p2,p4
Find the depth of the given node (say d). find the children from the root upto k-d levels leaving the branch that is towards the given node. traverse one step ahead towards the given node and now find the children upto k-d+1 levels leaving the branch that is towards the given node.
Do it until the given node is reached. Then find children at k levels below the given node.
Note: If k<d, traverse until d-k towards the given node and do the same
Complexity: O(k.d)
Finding the exor all all elements gives a^b (where and b are the required numbers). Finding the rightmost set bit means finding the position of the bit which differs in both (so the bit in this position for one number will be 0 and for other as 1) . This rightmost bit is named as set_bit_no. so '&' with all numbers will separate out all number into two where these two numbers are separated out
- SecretAgent February 05, 2012is distance is like just height or depth or else it can be any distance (like hop)
suppose k=2... so for this do we need to find the immediate sibling?
private static void FindCombinations(int num,ref Queue<string> queue)
{
int size,iterator;
string str;
if (num == 1)
{
queue.Enqueue("()");
}
else
{
FindCombinations(num - 1,ref queue);
Queue<string> tempQueue = new Queue<string>();
size = iterator = queue.Count;
while (iterator > 0)
{
str = queue.Dequeue();
tempQueue.Enqueue("()" + str);
queue.Enqueue(str);
iterator--;
}
iterator = size;
while (iterator > 0)
{
str = queue.Dequeue();
tempQueue.Enqueue("(" + str + ")");
queue.Enqueue(str);
iterator--;
}
queue = tempQueue;
}
return;
}
This queue will contain all the combinations of the desired result
- SecretAgent November 16, 2011yup.. that's right :)
- SecretAgent November 02, 2011i am sorry... the above program gives wrong solution in some inputs.. i just realized :)
- SecretAgent November 01, 2011these are 'exor' operations.. is there anything wrong in the solution?
- SecretAgent October 30, 2011In fact you can get it in O(n)
Maintain two numbers x and y and a temporary variable
while iterating through the array, temp= x^array[i]
if(temp==0), print that number.. else keep x=x^array[i] as it is
in order to see that the same number not to get printed store the printed number in y
temp = y^(printed number)
print the number only if temp!=0
Help this explains the algorithm!!
The solution can be achieved if we traverse the tree like BFS
Enqueue root node first into a queue A(first level)
Dequeue the root node in queue A and enqueue it's children in queue B
Now dequeue all elements in queue B and enqueue their children in queue A
Increment a counter whenever you use a queue
do until you don't have any elements in the queue
The above process is like level order traversal and the incremented count gives the levels or height of the tree
run through the two arrays using two pointers
Move the pointer pointing the smaller number and dump that number into the result
do that till both pointers exhaust
Here is the solution written in C# (Input taken as string to support larger numbers also)
private static string GetNextHighest(string num)
{
StringBuilder number = new StringBuilder(num);
bool flag = false;
int index;
int[] numberCount = new int[10];
if (number.Length == 1)
{
return number.ToString();
}
numberCount[Convert.ToInt32(char.ConvertFromUtf32(number[number.Length - 1]))]++;
for (index = number.Length - 2; index >= 0; index--)
{
if (number[index] < number[index + 1])
{
flag = true;
int swapNumber = Convert.ToInt32(char.ConvertFromUtf32(number[index]));
numberCount[swapNumber]++;
for (int iter = swapNumber + 1; iter < 10; iter++)
{
if (numberCount[iter] > 0)
{
numberCount[iter]--;
number[index++] = Convert.ToChar(iter+48);
break;
}
}
break;
}
numberCount[Convert.ToInt32(char.ConvertFromUtf32(number[index]))]++;
}
if (flag)
{
for (int iterator = 0; iterator < 10; iterator++)
{
for (int iter = 0; iter < numberCount[iterator]; iter++)
{
number[index++] = Convert.ToChar(iterator + 48);
}
}
return number.ToString();
}
else
{
return "-1";
}
}
- SecretAgent September 27, 20111.Start from right to left reading each digit
2.If the entire number is read in ascending order then return -1
3.Else stop when it is decreased, swap the decreased digit with the digit immediately bigger than the decreased digit from the set of surpassed digits
4. Sort the remaining digits to the right of the swapped digit
Ex: 1092
1.come from right, the digit decreased from 9 to 0
2. the surpassed digits are 2,9 so swap 0 with immediate bigger digit i.e, 2 (results in 1290)
3. sort remaining digits (1209)
Hi... i think the output is 5687
- SecretAgent September 27, 2011This question definitely needs (2 -ve with 1 +ve) or (3 +ve) numbers.
Lets take the help of data structures to solve this
consider 3 heaps say H1,H2,H3
H1 -> max heap of negative numbers of size 3
H2 -> min heap of negative numbers of size 2
H3 -> max heap of positive numbers of size 3
Iterate through the array of integers and push the integers into their respective heaps (Push 0 in H1 if it comes)
Now H1 and H2 contain our primary results
if (H3 is empty) or (H3 has 2 entries) then take needed values in H1 (This explains all negative values case)
In all the other cases evaluate the required result accordingly
Please note that whatever the value of 'n' is the lookup is finally broken down to 8 numbers at-max
Complexity: It is only one run through the array. so it is O(n)
Note: The heaps solution is proposed as it will be easy to explain and the same can be used for higher problems also (say find 7 integers to find largest product where coding in terms of variables may be difficult)
@FirstSolution your solution is fine but instead of copying to last and start from begining, how about starting from last and do your approach? This avoids initial copying operation
- SecretAgent September 23, 2011Assumption: The three numbers are known
suppose the three distinct numbers are x1,x2,x3
lets assume that after sorting these three these will be x1<x2<x3
Solution can be achieved in two runs through the array and this will be O(n)
In the first run get x1 always to the left of the array by swapping whenever x1 is encountered
Then in the second run, come from right to left maintaining x3 always at the end by swapping whenever x3 is encountered
finally x2 will end up in middle of the array
Eg:55454655664
after the first run the above approach will return
44455655665
after second run from behind the above approach will return
44455555666
Hope this example explains!!!
If the three number are not known, run another loop which determines the three :) (O(3n))
Please suggest any better algo if any!!!
I think the right solution would be like
1. start from right most digit as @cindrella said and find the digit bigger than immediate left
2. then swap both the digits and sort all the digits to the immediate right of the swapped digit in ascending order
3. in case of 7684, 8 is the swapped number and this will sort 64 to 46 which gives 7846
@nithin tell me if iam wrong
Check your solution for 7856... I guess your code will return 8756 whereas the answer should be 7865
- SecretAgent September 20, 2011
- SecretAgent August 07, 2014