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
- 4932 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 |
Faster Computers Suppose you have a computer that requires 1 minute to solve problem instances of size 1000. What instance sizes can be run in 1 minute if you buy a new computer that runs 1000 times faster than the old one, assuming the following time complexities T(n) for our algorithm? (a) T(n) = O(n). (b) T(n) = O(n3). (c) T(n) = O(10n).
using friend function find the maximum number from given two numbers from two different classes.write all necessary functions and constructor for the classes.
write a program in c++ to scramble a bmp image file using a scramble key 0x7c and an XOR logic. print out the original image, the scrambled image and the program. Note: the first 24bytes of a bmp file contain the header information of the file.
what is virtual constroctor ? give an exam for it?-(parimal dhimmar)
Show by induction that 2n > n2, for all n > 4.
2 Answers Karvy, Qatar University,
A suduco given & u hv 2 check if it is incomplete(blanks left),or correct or incorrect
write a program using virtual function to find the transposing of a square matrix?
write a program that can LOCATE and INSERT elements in array using c++ programming languages.
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,
Algorithm in O(2n) Presently we can solve in our hypothetical machine problem instances of size 100 in 1 minute using algorithm A, which is a O(2n). We would like to solve instances of size 200 in 1 minute using algorithm A on a new machine. What is the speed of the new machine should be?
2 Answers ABC, Qatar University,
write a program to sort 'n' elemnts using bubble sort
#include<stdio.h> #include<conio.h> void main() { char str[10]; int,a,x,sw=0; clrscr(); printf("Enter a string:"); gets(str); for(x=0;x<=a;a++); for(x=0;x<=a;x++) { if(str[x]==str[a-1-x]) { sw=1; } else sw=0; } if(sw==10 printf("The entered string is palindrome:"); else printf("The entered string is not a palindrome:); } getch(); } wht would be the explanation with this written code???
C Code 
