Prash
BAN USER@loler, nicely done. I was thinking of:
- sorting the elements
- looping over the sorted list from each end
- adding the first and last element and checking whether the sum is divisible by k
But, your approach is better and eliminates the need to sort.
@Ben, if distinctive is needed, then the above approach can be altered slightly to use a hashset to remove duplicate pairs, while storing pairs such as (1,1).
They are unsigned integers. So, as far as I can tell, there is no way to represent negative numbers.
For signed integers, the first bit tells whether the number is positive or negative. For unsigned, the first bit is part of the number and hence, only positive numbers are allowed.
So, -b can't be represented using unsigned numbers.
Another approach would be to construct a trie with all the numbers. At each node of the trie, including non-leaf nodes, store the count of that particular number. This will need a constant space as the height of the trie is the number of digits in the largest number. Moreover, traversing a trie of constant height is linear - O(1).
When trying to find the numbers that occur at least N/M times among N numbers, this implies that there can be, at the most, N/3 - 1 such numbers. For instance, there can be only 3 numbers that repeat more than 4 times in a list of N numbers.
Along with the trie, have M separate variables that keeps track of the numbers with the highest count so far. In this case, have 2 variables that keep track of the top 2 counts.
For example:
Consider N = 10 => M = 4 (>10/3)
Sequence = 24 56 38 38 51 56 56 56 80 8
Then the trie will be
----2(0) 3(0) 5(0) 8(1)
/ / / \ \
/ / / \ \
4(1) 38(2) 51(1) 56(4) 80(1)
And max count is 4 for 56. The second max is 2, which is < 10/3 and hence, can be ignored.
- Prash September 19, 2012Hey Fentoyal, I think your explanation is good, especially when equating to Tetris. But, I have difficulty believing that this is O(1) space or that it will find the correct answer.
Consider that you have N = 300 and M = 3. And the first 101 elements are 1 and the rest are 2 and 3. In this case, the first column goes to size 101 as there are no complete rows to delete. So, the space complexity is N/3 or O(N). Or if the numbers 1 and 2 keep repeating till 298. Then your space complexity becomes O(2n).
You can certainly make this better is if you keep the count of the numbers rather than keep a list of them in your columns, as Ankur suggested. Then this is essentially a map of the positions and their count.
Am I missing something here?
Consider the following:
N = 10
M = 4 (which is greater that 10/3)
Sequence = 1 2 3 5 1 4 1 4 1 4
Answer is 1 (as it is the only number that repeats 4 times)
Based on my understanding, which could be wrong, the states will be:
1
1 2
1 2 3
1 2 3 5
clear
1 4
1 4
1 4
And you are left with 2 elements, 1 and 4. So, how do you distinguish which one is the right answer?
PS: I really want to like and understand your solution and I hope I missed something in understanding your solution. I hate to be the messenger of bad news here :)
The binary search in Java
public class C {
private static class Tuple {
private int time;
private int value;
private Tuple(int time, int value) {
this.time = time;
this.value = value;
}
}
private static final Tuple[] TUPLES = new Tuple[] {
new Tuple(1, 3),
new Tuple(8, 6),
new Tuple(10, 11),
new Tuple(19, 4),
new Tuple(23, 9)
};
public static void main(String[] args) {
System.out.println(getValue(6, 0, TUPLES.length - 1));
System.out.println(getValue(10, 0, TUPLES.length - 1));
}
private static int getValue(int time, int start, int end) {
int value;
if (time == TUPLES[start].time) {
value = TUPLES[start].value;
} else if (time == TUPLES[end].time) {
value = TUPLES[start].value;
} else {
int mid = (int) (start + end) / 2;
int midTime = TUPLES[mid].time;
if (time == midTime) {
value = TUPLES[mid].value;
} else if (time > midTime) {
value = getValue(time, (mid + 1), end);
} else if (start == end || (start + 1) == end) {
value = TUPLES[end].value;
} else {
value = getValue(time, start, mid);
}
}
return value;
}
}
Why do you have to sort the boards?
Can't we just find the total length, divide the length by k, and get the ideal size that each painter has to paint.
Then, start from the first board, keep adding the boards till the total length is close to ideal size per painter. And so on for the rest of the painters.
My approach is a bit different and does have O(k*n) complexity, where k is a constant.
Scan the appointments to get the earliest start time - complexity = O(n)
Scan the appointments to get the latest end time - complexity = O(n)
The range is start time - end time (in minutes).
Outer loop for every minute, from start time to end time (constant)
- Inner loop through all the appointments to check whether the loop time falls between any of the appointments' start and end times.
In order to draw non-intersecting chords, you have draw triangles in the circle with all the triangles sharing one vertex.
Ex: If n = 5, then there are 10 points on the circle.
Start from P0, and draw chords to all other points, P1 - P9.
This will give you 9 lines or (2 * n - 1).
Then join all the points from P1 - P9 to their neighbors. This will give you 7 lines or (2 * (n - 1)).
Adding the two, you will get (4 * n - 3).
The idea is to find the two nodes between which the new value lies, while taking care of the end conditions.
if (headNode == null || length == 0) {
// If the length of the list is 0, newNode is the list.
headNode = newNode
newNode.next = newNode
newNode.prev = newNode
} else if (length == 1) {
// The length is 1, the headNode and newNode are linked to each other.
headNode.next = newNode
headNode.prev = newNode
newNode.next = headNode
newNode.prev = headNode
} else {
// If length is more than 1, find the nodes whose values surround newNode's value. Keep a counter to check the case when all the values in the list are the same and keeping the loop to go into an infinite loop.
loopNode = headNode
counter = 0
while (counter < length) {
if (newNode.value >= loopNode.value && newNode.value <= loopNode.next.value) {
break
} else {
counter++
loopNode = loopNode.next
}
}
newNode.prev = loopNode
newNode.next = loopNode.next
newNode.prev.next = newNode
newNode.next.prev = newNode
}
Nicely done. But, do you need to & with (n-1). Can't you & with 1?
Something like this?
- Prash October 21, 2012