Interested to Buy Any Domain ? << Click Here >> for more details...
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
- 5028 Views
- I also Faced
- E-Mail Answers
Answer Posted / 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 |
Post New Answer View All Answers
write a program using 2 D that searches a number and display the number of items 12 inputs values input 15,20, 13, 30, 38, 40,16, 18, 20 ,18 ,20 enter no. to search : 20
What output does this program generate as shown? Why? class A { A() { cout << "A::A()" << endl; } ~A() { cout << "A::~A()" << endl; throw "A::exception"; } }; class B { B() { cout << "B::B()" << endl; throw "B::exception"; } ~B() { cout << "B::~B()"; } }; int main(int, char**) { try { cout << "Entering try...catch block" << endl; A objectA; B objectB; cout << "Exiting try...catch block" << endl; } catch (char* ex) { cout << ex << endl; } return 0; }
write a program that creates a sequenced array of numbers starting with 1 and alternately add 1 and then 2 to create the text number in the series , as shown below. 1,33,4,6,7,9,............147,148,150 Then , using a binary search , searches the array 100 times using randomly generated targets in the range of 1 to 150
solve the problem in the programming language C++"if a five digit number is input through the keyboard.Write a program to calculate the sum of its digits(hint: use the modulus operator)
How to Split Strings with Regex in Managed C++ Applications?
Write a C/C++ program that connects to a MySQL server and displays the global TIMEZONE.
A suduco given & u hv 2 check if it is incomplete(blanks left),or correct or incorrect
U hv to enter a range from a and b and search hw many no. of times a pattern n. occurs between the range a and b. Eg :i/p:enter range :0 100 Enter pattern: 13 o/p: the no. times 13 occurred betwwn 0 to 100:1 Eg :i/p:enter range :100 1000 Enter pattern: 13 o/p: the no. times 13 occurred betwwn 100 to 1000: (in this 13,113,131,132,133…139,213,313,…913 all these will be counted)
What output does the following code generate? Why? What output does it generate if you make A::Foo() a pure virtual function? class A { A() { this->Foo(); } virtual void Foo() { cout << "A::Foo()" << endl; } }; class B : public A { B() { this->Foo(); } virtual void Foo() { cout << "A::Foo()" << endl; } }; int main(int, char**) { A objectA; B objectB; return 0; }
Code for Method of Handling Factorials of Any Size?
Code for Two Classes for Doing Gzip in Memory?
how to write a program that opens a file and display in reverse order?
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 C/C++ program that connects to a MySQL server and checks if the InnoDB plug-in is installed on it. If so, your program should print the total number of disk writes by MySQL.
Write a simple encryption program using string function which apply the substitution method.
