Flux
BAN USERIntroduce some simple hashing of integer sequences (for example, polynomial hash or even simple xor) and locate mismatching byte with binary search.
On first step, calculate hash of first and second halves of sequence, send them to other server, check which one doesnt match with other server's one. Repeat for mismatching part of array.
Total O(ln(n)) network interactions, obviously.
Hashes can be calculated in O(n) time and O(1) space, or in O(1) time and O(n) space using partial hashes.
Too few different codes. Must add my own implementation on C#:
static IEnumerable<string[]> AllCombinations(string[][] lists)
{
long cnt = lists.Aggregate(1L, (curr, list) => curr * list.Length);
for (long mask = 0; mask < cnt; ++mask)
{
string[] next = new string[lists.Length];
long m = mask;
for (int i = 0; i < lists.Length; ++i)
{
next[i] = lists[i][m % lists[i].Length];
m /= lists[i].Length;
}
yield return next;
}
}
We map input into set of form <x : count(x)>. Since each x can be taken from 0 to count(x) times we have total
Prod(count(x) + 1) for every distinct x
different subsets.
We can enumerate this subsets using value system with variable base, using same mask approach as in regular subset enumeration. But in our case, i-th digit of mask indicating how many times we peek i-th element of our set (in fact, in regular subset enumeration we do the same thing).
Here is sample code in C#:
static IEnumerable<List<int>> AllSubsets(int[] arr)
{
// next 2 steps can be done in linear time using hash table. here i use LINQ for short
var items = arr.Distinct().ToArray(); // get distinct items
var count = items.Select(x => arr.Count(k => k == x) + 1).ToArray(); // get their counts
Array.Sort(items, count); // for estetic purposes
int resSize = count.Aggregate(1, (x, y) => x * y); // each number k can be taken from 0 to count(k) times, so it is |Prod(count(k)+1) for each k| subsets in total
for (int i = 0; i < resSize; i++)
{
var mask = i;
var res = new List<int>();
for (int p = 0; p < items.Length; p++)
{
for (int c = mask % count[p]; c > 0; c--) res.Add(items[p]); // here c is p-s digit in mask
mask /= count[p];
}
yield return res;
}
}
Assume that such splitting exists.
Let then N be array length, Sum - sum of entire array, P - sum of one part of items, K - count of numbers in that part.
Let's write equations for averages in both parts of array:
P / K = (Sum - P) / (N - K)
P * (N - K) = K * (Sum - P)
P * N - P * K = K * Sum - K * P
P * N = K * Sum
P = K * Sum / N
Now we can easily check if such P can be integer (we operate with array of integers).
If so, we reduce our problem to picking K integers with sum of P from sorted array of integers.
C# code:
static List<int> GetSum(int[] numbers, int count, int needSum)
{
// numbers must be sorted
List<int> result = new List<int>();
// can apply memoization to rec
Func<int, int, int, bool> rec = null;
rec = (index, cnt, sum) =>
{
if (sum == 0) return cnt == 0;
if (index == numbers.Length) return false;
for (int j = index; j < numbers.Length; j++)
{
result.Add(j);
if (rec(j + 1, cnt - 1, sum - numbers[j])) return true;
result.Remove(j);
}
return false;
};
return rec(0, count, needSum) ? result : null;
}
// returns indices of left part or null, if array cannot be splitted
static List<int> Divide(int[] numbers)
{
Array.Sort(numbers);
int sum = numbers.Sum();
int n = numbers.Length;
for (int k = 1; k <= n - k; k++)
{
if (k * sum % n != 0) continue;
int p = k * sum / n;
List<int> tmpRes = GetSum(numbers, k, p);
if (tmpRes != null) return tmpRes;
}
return null;
}
static void Main(string[] args)
{
int[] arr = new int[] { 1, 7, 15, 29, 11, 9 };
List<int> leftIndices = Divide(arr);
if (leftIndices == null)
Console.WriteLine("No solution");
else
{
Console.WriteLine("Whole array:");
Console.WriteLine(string.Join(" ", arr));
Console.WriteLine("Left part:");
Console.WriteLine(string.Join(" ", leftIndices.Select(i=>arr[i])));
}
}
Can you look at formula
M = Sum(Ni * (2^i + 1)) for i in 0..length(N)
and see that you CAN NOT represent 6 in such way? In your example, you count 2^1 + 1 TWICE, when it is obvious can be counted 1 or 0 times, because Ni is i-th digit in binary representation of N.
And if you will run my "wrong" code you'll see that output for 6 is TRUE.
Suppose we are checking number "M" for weakness.
Number M is supported if there is some number N, such that N + numOfOneBits(N) = M.
Let's look at binary representation of N.
N = Sum(Ni * 2^i) for i in 0..length(N)
numOfOneBits(N) = Sum(Ni * 1) for i in 0..length(N)
After grouping corresponding terms, we get
M = N + numOfOneBits(N) = Sum(Ni * 2^i + Ni * 1) for i in 0..length(N)
M = Sum(Ni * (2^i + 1)) for i in 0..length(N)
So, if M is representable in such way, it is supported number. Any questions?
Also, you said "If you mean 2^k+1 the 4 which is bleak does not fit". Have you even run the code before commenting?
Main idea is to check if number can be represented in form of Sum(2^k+1) for some k's:
static bool IsBleak(int m)
{
int len = 0; // number length in binary form enougth to represent n;
while ((1 << len) + len < m) len++;
for (int i = len; i >= 0; i--) if (m >= (1 << i) + 1) m -= (1 << i) + 1;
return m != 0;
}
Using meet-in-the-middle approach and hash table we can achieve O(n^2) complexity. C# code:
struct Pair
{
public int x, y;
}
static IEnumerable<int[]> FindCombinations(int[] arr, int x) // meet-in-the-middle algo
{
int n = arr.Length;
Dictionary<int, List<Pair>> hash = new Dictionary<int, List<Pair>>(n * (n - 1) / 2);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
{
if (!hash.ContainsKey(arr[i] + arr[j])) hash.Add(arr[i] + arr[j], new List<Pair>());
hash[arr[i] + arr[j]].Add(new Pair { x = i, y = j });
}
foreach (int sum in hash.Keys)
foreach (Pair pair1 in hash[sum])
{
List<Pair> rest;
if (hash.TryGetValue(x - sum, out rest))
{
foreach (Pair pair2 in rest)
if (pair2.x > pair1.y)
yield return new int[] { arr[pair1.x], arr[pair1.y], arr[pair2.x], arr[pair2.y] };
}
}
}
C# implementation of one-pass algo:
static int[] Search(int[] arr, int k)
{
if (k < 0) return null;
int i = 0, j = 0, sum = 0;
while (j < arr.Length)
{
while (j < arr.Length && sum < k) sum += arr[j++];
while (i < arr.Length && sum > k) sum -= arr[i++];
if (sum == k) return arr.Skip(i).Take(j - i).ToArray();
}
return null;
}
As ghost89413 noticed above below, there is recurrent formula for running time
T(n) = T(n-1) + T(n-2)
For n < 2, T(n) = 1
Which is Fib(n).
Another intuitive approach is to notice that we haven't any type of memoisation or result caching for functions call, so final result is sum of 1-s (if "flatten" recursion tree). Fib(n) consists of Fib(n) ones, so complexity is Fib(n).
Here is divide & conquer algorithm. I believe it has logarithmic complexity, because on each step we discard at least quarter of elements. Code in C#:
static bool Find(int[,] arr, int value, int xmin, int ymin, int xmax, int ymax)
{
if (xmin > xmax || ymin > ymax) return false;
int pivotX = (xmin + xmax) / 2, pivotY = (ymin + ymax) / 2;
if (value < arr[pivotX, pivotY])
return
Find(arr, value, xmin, ymin, xmax, pivotY - 1) ||
Find(arr, value, xmin, pivotY, pivotX - 1, ymax);
if (value > arr[pivotX, pivotY])
return
Find(arr, value, xmin, pivotY + 1, xmax, ymax) ||
Find(arr, value, pivotX + 1, ymin, xmax, pivotY);
return true;
}
static bool Find(int[,] arr, int value)
{
return Find(arr, value, 0, 0, arr.GetLength(0) - 1, arr.GetLength(1) - 1);
}
static void Main(string[] args)
{
int[,] arr = new int[,]
{
{ 1, 2, 3, 14, 20 },
{ 4, 6, 10, 15, 30 },
{ 5, 7, 12, 16, 42 },
{ 8, 9, 13, 27, 43 }
};
Console.WriteLine(Find(arr, 19)); // false
Console.WriteLine(Find(arr, 27)); // true
}
There is also a tricky solution with very good time and space complexities. We do not have any restrictions about output format of resultant word set, so it will be absolutely legal to output them as a trie. The main idea of algorithm is following:
Given a source string and map of substitutions, let's construct a trie with a single word - source string:
(start)
|
(f)
|
|
(a)
|
|
(b)
|
(end)
Now, lets iterate over trie nodes. If we see a node with a character that presents in a map, let's transform this node to a cuple of nodes with all possible substitutions for that character, i.e.
| / | \
(f) -> (f)(F)(4)
| \ | /
Applying this procedure to all nodes, we will get a trie with all possible substitutions, like
(start)
/ | \
(f)(F)(4)
\ | /
|
(a)
|
/ | \
(b)(B)(8)
/ | \
(end)(end)(end)
So that, in worst case, time and space complexity is O(n*k), where n is length of the string and k is length of longest array in the map of substitutions.
- Flux October 22, 2013O(ans.count) time and O(ans.size) space complexity:
static List<string> GenerateSubstitutions(string str, Dictionary<char, string> map)
{
List<string> result = new List<string>();
StringBuilder sb = new StringBuilder(str);
Action<int> rec = null;
rec = pos =>
{
if (pos >= sb.Length) result.Add(sb.ToString());
else
if (!map.ContainsKey(str[pos])) rec(pos + 1);
else
{
rec(pos + 1);
foreach (var c in map[str[pos]])
{
sb[pos] = c;
rec(pos + 1);
}
}
};
rec(0);
return result;
}
Pretty elegant solution using generators in C#:
static IEnumerable<long> Fibonacci(long a, long b)
{
long c;
yield return a;
yield return b;
while (true)
{
yield return c = a + b;
a = b;
b = c;
}
}
static IEnumerable<long> FibonacciRange(long a, long b, long from, long to)
{
return Fibonacci(a, b).SkipWhile(x => x < from).TakeWhile(x => x <= to);
}
The main idea of code given below is to use number system with variable base to enumerate all combinations. Sample code in C#:
Dictionary<char, string> map = new Dictionary<char, string>
{
{ '0', "zaqxsw" },
{ '1', "cde" },
{ '2', "vfr" },
{ '3', "bgt" }
};
string pattern = "1230";
int cnt = pattern.Select(c => map[c].Length).Aggregate((x, y) => x * y);
for (int i = 0; i < cnt; i++)
{
int mask = i;
foreach (char c in pattern)
{
int pos = mask % map[c].Length;
Console.Write(map[c][pos]);
mask /= map[c].Length;
}
Console.WriteLine();
}
The main idea is to find occurrence using binary search, and then go left as far as possible, increasing step each time. When step cannot be increased anymore, go left reducing step. Time complexity is O(ln(n))
Sample code in C#:
static int BinSearch<T>(T[] arr, T value) where T : IComparable<T>
{
int lower = arr.GetLowerBound(0), upper = arr.GetUpperBound(0);
while (lower <= upper)
{
int center = (lower + upper) / 2;
if (value.CompareTo(arr[center]) > 0) lower = center + 1;
else
if (value.CompareTo(arr[center]) < 0) upper = center - 1;
else
{
// occurrence found, go left as far as possible
int step = 1;
for (; ; step *= 2)
{
if (center - step >= lower &&
arr[center - step].CompareTo(value) == 0) center -= step;
else
break;
}
for (; step > 0; step /= 2)
{
if (center - step >= lower &&
arr[center - step].CompareTo(value) == 0) center -= step;
}
return center;
}
}
return arr.GetLowerBound(0) - 1;
}
Yes, it can be done in O(n).
First of all, let's sort our array in O(n) time using radix sort. Then, create two pointers i and j pointing to first and last elements of the sorted array. Let's iterate pointer i over our array, shifting pointer j to the left, maintaining a[i] + a[j] < threshold and incrementing result by j at each iteration. It is obvious that both pointers will pass entire array only once, so total complexity is still O(n).
You know, there is C(n, 2) such n-bit integers, so with N ~ 10^14 output value can be order of 2^(10^7), so problem is not just about "bit manipulation".
- Flux February 21, 2017Solution: lets look at numbers MSB. There is exactly k numbers in this sequence with MSB at position k (1 for MSB = 2^1 (3), 2 for MSB = 2^2 (5,6) and so on). Inside of this blocks of increasingly larger sizes, LSB goes from 0 to k-1.
So, formal solution is following:
- define k = min x : x*(x+1)/2 >= N
- define p = k*(k+1)/2 - N
Answer is 2^k + 2^(k - p - 1).