GK
BAN USERstatic void Main(string[] args)
{
string[][] arr = { new[] { "red", "blue", "green" }, new[] { "XL", "X", "M", "S" }, new[] { "checks", "lines"} };
var res = new string[arr.Length];
PerformPrinting(arr , 0 , res);
}
private static void PerformPrinting(string[][] arr, int i, string[] res)
{
if (i == arr.Length)
Print(res);
else
{
for (int j = 0; j < arr[i].Length; j++)
{
res[i] = arr[i][j];
PerformPrinting(arr, i + 1, res);
}
}
}
static void Print(string[] res)
{
Console.WriteLine(String.Join("-" , res));
}
Chaitanya, here is an example:
input {0,10,255} {2 , 11 , 257} {4,12,258}
Let's take the first element from each array and push them into priority queue.
step 0: queue: [0,2,4] range:0-4
step 1: pop 0 from queue , push next element to 0 from first array
queue: [2,4,10] range: 2-10
step2: pop 2 , push 11
queue: [4,10,11] range: 4-11
step3: pop 4 , push 12
queue: [10,11,12] range: 10-12 <----- minimal range
etc...
Update: Found a bug in my idea. We need to use priority queue , because newly added element may be smaller than actual max element. So, because of it, there is no need to sort first elements , just add them (the value will play the role of priority) in queue. If we want to calculate actual length, just need to ask queue for first and last element.
- GK February 25, 2014marut , I suppose you haven't read question carefully. You need to find minimum range, which will contain at least one element from each array. For example {0,10,255} {2 , 11 , 257} {4,12,258} the correct answer is 10-12 , the range is minimum and there is element in each array, which contains in this interval 10 from 1-st array , 11 from second and 12 from third.
- GK February 25, 2014Here is my idea.
(A) Let's take the smallest element from each array. For each element we will remember from which array did we take it. Sort them and add to the queue this way : the smallest element will be on the first place.
(B) After this, we know the first and the last element. Let's count length of the interval.
Next step is to pop element (let's call it x) and push next to x element, from the same array. Calculate length of the interval and repeat (B) until one of the arrays reaches its upper bound.
some c# code. Suppose it works ok.
static Tuple<Node, Node> Transform(Node node)
{
Node begin, end;
if (node.Left != null)
{
var result = Transform(node.Left);
begin = result.Item1;
result.Item2.Right = node;
node.Left = null;
}
else
{
begin = node;
}
if (node.Right != null)
{
var result = Transform(node.Right);
end = result.Item2;
node.Right = result.Item1;
}
else
{
end = node;
}
return new Tuple<Node, Node>(begin,end);
}
Some c# code:
public static string BuildPalindrome(string input)
{
if (String.IsNullOrEmpty(input))
throw new ArgumentException("input");
var alph = Enumerable.Repeat(0, 255).ToArray();
var palindrome = new char[input.Length];
foreach (var t in input)
alph[t]++;
var position = 0;
var flag = false;
for (var i = 0; i < 255; i++)
{
if (alph[i] % 2 != 0)
{
if (flag)
return "-1";
flag = true;
alph[i]--;
palindrome[input.Length/2] = (char) i;
}
while (alph[i] != 0)
{
palindrome[position] = palindrome[input.Length - 1 - position] = (char) i;
alph[i] -= 2;
position++;
}
}
return String.Join("", palindrome);
}
Here is my idea.
It's pretty clear, that pair of numbers has integer mid-value, if sum of these digits is even.
There are two good ways for us: both of numbers are even or both of numbers are odd.
Now we can associate each point to bit vector. F.e. (3,4,5,6) = (3%2,4%2,5%2,6%2) =(1,0,1,0) (binary system) = 10 (decimal system)
Now we should group each point by it's decimal representation, we may use dictionary for example.
class Point
{
public List<int> Dots { get; set; }
public override string ToString()
{
return String.Format("({0})",String.Join(",",Dots));
}
}
class Program
{
public static void FindPairs(List<Point> points)
{
var pairs = new Dictionary<int, List<Point>>();
foreach (var point in points)
{
var val = 0;
var temp = 1;
point.Dots.ForEach(dot =>
{
if (dot%2 == 1)
{
val += temp;
}
temp *= 2;
});
if (pairs.ContainsKey(val))
pairs[val].Add(point);
else
pairs.Add(val , new List<Point>{point});
}
foreach (var pair in pairs.Where(pair => pair.Value.Count > 1))
{
foreach (var point in pair.Value)
{
Console.WriteLine(point.ToString());
}
Console.WriteLine();
}
}
}
Recursive solution. Little bit easier to understand.
bool shoekeeper(int N, int sum, const vector<int>& packs){
if (sum > N)
return false;
else if (sum == N)
return true;
for (int i = 0; i < packs.size(); i++){
if (shoekeeper(N, sum + packs[i], packs))
return true;
}
return false;
}
Really? How did you get it? :)
- GK March 10, 2014