napostolov
BAN USERimport Foundation
class Play {
func play() {
let numbers: Int[] = [1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9]
var dataBank: Int = 0
for number in numbers {
var slot = 1 << number
dataBank ^= slot // Toggle the bit everytime we find the same number in the sequence
}
dataBank = ~dataBank // Invert it so now the posistive bits represent the EVEN numbers we are looking for
for number in numbers {
if dataBank & (1 << number) > 0
{
// TODO: The even numbers will appear at multiple times
println("Even number found: \(number)")
}
}
}
Here's my solution.
Running complexity O(2n) worst case, when we don't find a solution.
int *toArray(char *number, int size)
{
int *buffer = new int(size);
for (int i=0; i<size; i++) {
buffer[i] = number[i] - '0';
}
return buffer;
}
int length(int n)
{
int len = 1;
while ((n /= 10))
++len;
return len;
}
bool canIncrease(int slot)
{
assert(slot >= 0);
assert(slot <= 9);
return (slot != 9);
}
bool canDecrease(int slot)
{
assert(slot >= 0);
assert(slot <= 9);
return (slot != 0);
}
bool process(int *array, int size)
{
assert(size > 0);
assert(array != NULL);
if (size < 2)
return false;
int p1 = size-2;
int p2 = size-1;
while (!canIncrease(array[p1])) {
--p1;
--p2;
if (p1 < 0)
break;
}
while (!canDecrease(array[p2])) {
++p2;
if (p2 == size)
break;
}
if (p1 >= 0 && p2 < size && p1 < p2){
array[p1]++;
array[p2]--;
return true;
}
return false;
}
int main(){
int n = 0;
int size = length(n);
int *result = toArray(n);
if (process(result, size)){
printf("%d\n\n", *result);
}
delete result;
n = 111;
size = length(n);
result = toArray(n);
if (process(result, size)){
printf("%d\n", result[0]);
printf("%d\n", result[1]);
printf("%d\n\n", result[2]);
}
delete result;
n = 5;
size = length(n);
result = toArray(n);
if (process(result, size)){
printf("%d\n", result[0]);
printf("%d\n", result[1]);
printf("%d\n\n", result[2]);
}
delete result;
char number[] = "09999";
result = toArray(number, 5);
if (process(result, 5)){
printf("%d\n", result[0]);
printf("%d\n", result[1]);
printf("%d\n", result[2]);
printf("%d\n", result[3]);
printf("%d\n", result[4]);
}
delete result;
}
import java.util.*;
import java.io.*;
class Node {
public int data;
public Node left;
public Node right;
Node(int data){
this.data = data;
}
}
class LevelNode extends Node{
int level;
LevelNode(int data, int level)
{
super(data);
this.level = level;
}
}
class BFS{
public Queue<LevelNode> q;
private Node root;
BFS(){
this.buildTree();
this.processBF();
}
public Iterable<Integer> getPiers()
{
LevelNode oldNode = null;
List<Integer> list = new ArrayList<Integer>();
for(LevelNode node : this.q)
{
if (oldNode != null)
{
if (node.level != oldNode.level){
list.add(oldNode.data);
list.add(node.data);
}
}
oldNode = node;
}
list.add(oldNode.data); // The very last one is also a pier
return list;
}
private void processBF()
{
if (root == null)
return;
q = new LinkedList<LevelNode>();
q.add(new LevelNode(root.data, 0));
process(root, 1);
}
private void process(Node node, int level)
{
if (node == null)
return;
if (node.left != null)
q.add(new LevelNode(node.left.data, level));
if (node.right != null)
q.add(new LevelNode(node.right.data, level));
process(node.left, level+1);
process(node.right, level+1);
}
private void buildTree()
{
root = new Node(0);
root.left = new Node(1);
root.right = new Node(2);
root.left.left = new Node(3);
root.left.right = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(6);
root.right.left.left = new Node(7);
root.right.left.right = new Node(8);
root.right.right.left = new Node(9);
root.right.right.right = new Node(10);
}
public static void main(){
}
}
1 + the number of combinations with repetition allowed (n choose r).
The formula is (n+r-1)! / r!(n-1)! and r = 3 (the number of nested loops)
1 + (n+2)! / 6(n-1)!
Selection sort has a lot of seeks. You constantly go and look for the least element.That would be a lot of lift movements.
Insertion sort requires making room for the insertion. In our context you have to add another floor which is hard thing to do in the construction business :)
What we need is in-place sorting algorithm with least seeks. Swaps are cheap, as we can drop and take people and that do not add to the lift overall movements.
Bubble sort seems to be the most appropriate here?
Important question would be - do we know up front which floor has which person number?
In other words, does the lift find out who's person number is at the floor only once it visits this floor?
Probability: 0.246094
- napostolov November 08, 2015