vladimir.grebennikov
BAN USERThis solution has the best case scenario complexity of O(log(sqrt(n)). The worst case scenario takes O(sqrt(n)) time. The idea is to find prime factors and their numbers. Then we just need to calculate the numbers each prime factor occurs in the input number.
private int FactorsNumber(int n)
{
var m = n;
var res = 1;
for (int d = 2; d <= Math.Sqrt(m); d++)
{
var k = 1;
while (m % d == 0)
{
m /= d;
k++;
}
if (k > 1) res *= k;
}
if (m > 1) res *= 2;
return res - 1;
}
Did using bit operations.
private int DivideManual(int a, int b)
{
if (b == 0) throw new Exception("Diving by zero");
if (a == 0) return 0;
if (a < b) return 0;
if (a == b) return 1;
int m = 0;
int n = 0;
while (a >> m++ > 0) ;
while (b >> n++ > 0) ;
var c = a >> (m - n);
int d = 0;
if (c >= b)
{
c -= b;
d++;
}
for (int i = m - n - 1; i >= 0; i--)
{
c = (c << 1) + (a >> i) - ((a >> (i + 1)) << 1);
d = d << 1;
if (c >= b)
{
c -= b;
d++;
}
}
return d;
}
Dominoes can be presented as a graph with vertices 0, 1, ..., N, where edges stand for edges connecting vertices of the corresponding number. The degree of each vertex is N+2 (N edges connecting each vertex with other vertices and one loop edge, which increases degree by 2). Building the full dominoes loop is equivalent to finding Eulerian cycle in the graph. And the latter is possible if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component. That means that we just need to check if N is even. In this case N+2 is also even which means that there's a Eulerian cycle in the graph.
- vladimir.grebennikov December 12, 2014O(N*logN). We loose time only on sorting time intervals.
public class Event:IComparable<Event>
{
public double Time;
public bool IsStart;
public Event(double time, bool isStart)
{
Time = time;
IsStart = isStart;
}
public int CompareTo(Event other)
{
return Time.CompareTo(other.Time);
}
}
public IEnumerable<double[]> TimeIntervalsSplit(double[][] intervals)
{
var timeLine = new Event[intervals.Length * 2];
for (int i = 0; i < intervals.Length; i++)
{
if (intervals[i].Length != 2 || intervals[i][1] <= intervals[i][0]) throw new Exception("Invalid input");
timeLine[i * 2] = new Event(intervals[i][0], true);
timeLine[i * 2 + 1] = new Event(intervals[i][1], false);
}
Array.Sort(timeLine);
int depth = 1;
for (int i = 1; i < timeLine.Length; i++)
{
if (timeLine[i].IsStart)
{
if (depth++ > 0) yield return new[] { timeLine[i - 1].Time, timeLine[i].Time };
}
else
{
depth--;
yield return new[] { timeLine[i - 1].Time, timeLine[i].Time };
}
}
}
You might want to mess a bit with the resulting intervals edges if you want the previous closing time to be less than the next opening time. But I see no difficulties doing so.
- vladimir.grebennikov December 11, 2014Here's the solution with a bit of memory conservation:
private class TempSum
{
public int Sum;
public int MaxUsed;
public TempSum(int sum, int maxUsed)
{
Sum = sum;
MaxUsed = maxUsed;
}
}
public int ArraySumMinInt(params int[] ar)
{
Array.Sort(ar);
int n = ar.Length;
var queue = new List<TempSum> { new TempSum(0, -1) };
int seekingFor = 1;
while (queue.Any())
{
var current = queue[0];
if (current.Sum > seekingFor) return seekingFor;
queue.RemoveAt(0);
int j = queue.Count - 1;
for (int i = n - 1; i > current.MaxUsed; i--)
{
var next = new TempSum(current.Sum + ar[i], i);
while (j >= 0 && queue[j].Sum > next.Sum) j--;
if (++j < queue.Count) queue.Insert(j--, next);
else
{
queue.Add(next);
j--;
}
}
seekingFor = current.Sum + 1;
}
return seekingFor;
}
The idea is to try to build all possible sums in an increasing way. Each time we take the current smallest sum we add all possible sums, which can be created by adding one of the numbers not used in it (their indices must be greater than the greatest index used before to avoid repeating, that's why the MaxUsed field is introduced). The resulting new sums must be placed in the queue in the way that keeps the queue increasing. I guess this solution has elements of dynamical programming.
In the worst case scenario (the minimum number is the sum of all elements + 1) this algorithm has the complexity O(n*2^n) (the same as bruteforce), while memory comsumption is O(combination(n,n/2)), which is better compared to bruteforce's O(2^n).
In the best case scenario (when there's no 1 in the input array) the answer will be given at once.
O(n)
Each time current profit streak is less than zero we can assume that we should've started trading later. This means that we can assign zero to current streak and assume that we're starting trading from the next point.
- vladimir.grebennikov December 17, 2014