A research student is given a singly-linked list. Each node
of the list has a color, which is either “Black”
or “White”. He must find if there are more black nodes than
white nodes, or vice versa. His advisor
gives him 5,000Rs to buy a computer to do the work. He goes
to the computer store and finds a
slightly defective computer which costs a mere 3,000Rs. This
computer has the small problem of not
being able to do arithmetic. This means that he cannot use a
counter to count the nodes in the list to
determine the majority color. The computer is otherwise
fully functional. He has the evil idea that he
could buy the defective computer and somehow use it to do
his work, so that he can use the rest of
the money on enjoyment. Show how he can accomplish this
amazing task. Write code for an algorithm
called ‘findMajorityColor’ which takes a singly-linked list,
L, with n nodes and returns the majority color
among nodes of L. This algorithm should have the same
asymptotic running time as counting the
nodes (O(n)). Note: No arithmetic is allowed.
- 2 Answers
- 3999 Views
- I also Faced
- E-Mail Answers
Answers were Sorted based on User's Feedback
Answer / tayyab nasir
The best way to do this is to create a new linked list and insert Black nodes at head and White nodes at tail from the previous to the new list. Then find the middle point of the new list. If middle point is Black then Black nodes are more in number else the White nodes.
| Is This Answer Correct ? | 0 Yes | 0 No |
what mean void creat_object?in public class in this code class A{ public: int x; A(){ cout << endl<< "Constructor A";} ~A(){ cout << endl<< "Destructor A, x is\t"<< x;} }; void create_object(); void main() { A a; a.x=10; { A c; c.x=20; } create_object(); } void create_object() { A b; b.x=30; }
Write a program that takes a 3 digit number n and finds out whether the number 2^n + 1 is prime, or if it is not prime find out its factors.
Question 1: Implement a base class Appointment and derived classes Onetime, Daily, Weekly, and Monthly. An appointment has a description (for example, “see the dentist”) and a date and time. Write a virtual function occurs_on(int year, int month, int day) that checks whether the appointment occurs on that date. For example, for a monthly appointment, you must check whether the day of the month matches. Then fill a vector of Appointment* with a mixture of appointments. Have the user enter a date and print out all appointments that happen on that date. *This Should Be Done IN C++
Hello, I am trying to write a program in c++ which accepts month and year from the user and prints the calender. So please tell me the algorithm and what is the calender logic.
Deriving time complexity of Binary tree and AVL tree, step by step.
Wrie a function which returns the most frequent number in a list of integers. Handle the case of more than one number which meets this criterion. public static int[] GetFrequency(int[] list)
Code for Two Classes for Doing Gzip in Memory?
Given a table of the form: Product Sold on A 1/1/1980 B 1/1/1980 C 1/1/1980 A 1/1/1980 B 1/1/1980 C 2/1/1980 A 2/1/1980 There are 30 products and 10,000 records of such type. Also the month period during which sales happened is given to u. Write the program to display the result as: Product Month No. of copies A January 12 A February 15 A March 27 B January 54 B February 15 B March 10 C January 37
1. Write a program using one dimensional array that calculates the sum and average of the five input values from the keyboard and prints the calculated sum and average.
Min-Max Write an algorithm that finds both the smallest and largest numbers in a list of n numbers and with complexity T(n) is at most about (1.5)n comparisons.
10 Answers ABC, College School Exams Tests, ITC Infotech, Kyambogo University, Qatar University,
Min-Max Write an algorithm that finds both the smallest and largest numbers in a list of n numbers and calculate its complexity T(n).
1 Answers Infosys, Qatar University,
what is the difference between int &r and int& r
C Code 
