algorithm - Finding a majority of unorderable items -
i have 1 problem finding solution task.
you have n students , n courses. student can attend 1 course , 1 course can attended many students. 2 students classmates if attending same course. how find out if there n/2 classmates in n students this?
conditions: can take 2 students , ask if classmates , answer can "yes" or "no". , need in o(n*log(n)).
i need idea how make it, pseudo code fine. guess divide list of students merge sort, gives me logarithmic part of complexity. ideas great.
first, pair off each student (1&2, 3&4, 5&6... etc), , check , see pairs in same class. first student of pair gets "promoted". if there "oddball" student, in own class, promoted well. if single class contains >=50% of students, >=50% of promoted students in class. if no students promoted, if single class contains >=50% of students either first or second student must in class, promote both of them. leads case >=50% of promotions in large class. takes ⌊n/2⌋ comparisons.
now when examine promoted students, if class contains >=50% of students, >=50% of promoted students in class. therefore, can recurse, until reach stop condition: there less 3 promoted students. @ each step promote <=50% of students (plus 1 sometimes), step occurs @ ⌈log(n,2)⌉ times.
if there less 3 promoted students, know if >=50% of original students in class, @ least 1 of these remaining students in class. therefore, can compare each , every original student against these promoted students, reveal either (a) class >=50% of students, or (b) no class has >=50% of students. takes @ (n-1) comparisons, occurs once. note there possibility original students match 1 of 2 remaining students evenly, , detects both classes have =50% of students.
so complexity n/2 *~ log(n,2) + n-1. however, *~ signifies don't iterate on n/2 students @ each of log(n,2) iterations, decreasing fractions n/2, n/4, n/8..., sum n. total complexity n/2 + n/2 + n-1 = 2n-1, , when remove constants o(n). (i feel may have made math error in paragraph. if spots it, let me know)
see in action here: http://coliru.stacked-crooked.com/a/144075406b7566c2 (the comparison counts may slightly on estimate due simplifications made in implementation)
key here if >50% of students in class, >=50% of arbitrary pairs in class, assuming oddball student matches himself. 1 trick if 50% match, it's possible alternate in original order , nobody gets promoted. luckily, cases alternating, promoting first , second students, in edge case, >=50% of promotions in large class.
it's complicated prove >=50% of promotions in large class, , i'm not can articulate why is. confusingly, doesn't hold prettily other fractions. if target >=30% of comparisons, it's entirely possible none of promoted students in target class(s). >=50% magic number, isn't arbitrary @ all.