eswddd
BAN USERFirst anonymous has it right, except I think you can make it more efficient by performing a dual BFS concurrently, and checking at each stage whether the next element to be processed exists in the set of ancestors of the other person:
public class Person {
Person[] parents;
}
// naming for cousins is: n th cousin m times removed
// where n is the min generations to a common ancestor and m is the number of generations difference between the 2 cousins
// so this is going to be O((2^n+m)+2) which is still more efficient than dfs assuming the num generations in the population is > n+m
public boolean bloodRelated(Person p1, Person p2) {
// simple search would go down p1's children/grandchildren/etc and see if we find p2
// then vice versa
// then worry about cousin style relationships
// here we'd go up the parent tree on both until we found a common node (or ran out of data)
// we could take this last approach anyway and it would get us a parent-child match too
Set<Person> p1Ancestors = new HashSet<Person>();
Set<Person> p2Ancestors = new HashSet<Person>();
// so ideally here we're going to do BFS, but we're going to do 2 at once to try to minimise the depth we have to go
List<Person> p1Discovered = new LinkedList<Person>();
p1Discovered.add(p1);
List<Person> p2Discovered = new LinkedList<Person>();
p2Discovered.add(p2);
while (!p1Discovered.isEmpty() || !p2Discovered.isEmpty()) {
Person nextP1 = p1Discovered.remove(0);
if (nextP1 != null) {
if (p2Ancestors.contains(nextP1)) {
return true;
}
for (Person parent : nextP1.parents) {
p1Discovered.add(parent);
}
p1Ancestors.add(nextP1);
}
Person nextP2 = p2Discovered.remove(0);
if (nextP2 != null) {
if (p1Ancestors.contains(nextP2)) {
return true;
}
for (Person parent : nextP2.parents) {
p2Discovered.add(parent);
}
p2Ancestors.add(nextP2);
}
}
return false;
}
Ok, so I'm assuming that the number has to be perfectly divisible by 2 or 9 or a combination of these for someone to win (so prime numbers are out for e.g.), in which case I think it's just a case of how many multiples of these are factors of the number in question, and if P1 goes first, then he can only win if there's an odd number of multiples:
public class Game2_9 {
public static void main(String[] args) {
System.out.println(new Game2_9().winner(24234234));
System.out.println(new Game2_9().winner(2*2*2*2*9*9*9*2));
System.out.println(new Game2_9().winner(2*2*2*2*9*9*9*2*9*2*2));
System.out.println(new Game2_9().winner(1));
}
public int winner(int N) {
int goes = calcGoes(N);
// for goes == 0, need to consider whether first player
// has to pick between 2 or 9, or whether can decide not to pick because it's 1
// i've assumed they have to pick, so nobody wins
if (goes == -1 || goes ==0) {
return 0;
}
if (goes%2==0) {
return 2;
}
return 1;
}
private int calcGoes(int n) {
if (n == 1) {
return 0;
}
if (n%9==0) {
int goes = calcGoes(n/9);
return goes==-1?-1:goes+1;
}
if (n%2==0) {
int goes = calcGoes(n/2);
return goes==-1?-1:goes+1;
}
return -1;
}
}
RepCliftonMalone, Android Engineer at ABC TECH SUPPORT
Hello, I am a Seo Analyst with 5 years of experience in helping large ecommerce websites reach higher organic positions ...
Repcloptonchirsty, Android Engineer at 8x8
Hello, I am an Organic chemist and my all study and degree is complete from New York.Apart from this ...
RepAveryPerez, abc at 8x8
I am a self-driven and motivated librarian skilled at providing excellent public service to students and staff, managing the library ...
RepEzraDavis, abc at A9
I am a hardworking and disciplined newly-certified architect with internship experience in designing commercial buildings and creating accurate 2D and ...
RepJulianMiller, abc at ABC TECH SUPPORT
I am a professional auditing assistant with extensive experience in handling administrative duties and executive responsibilities associated with both internal ...
Repmaryjcowell, Android Engineer at AMD
Hey I am information designer.Information Designers facilitate the delivery of information by translating complex information into information that users ...
There's no majority in that sequence..
- eswddd July 25, 2013You have 6 x 1's and 13 numbers in total.