chennavarri
BAN USERFeel free to contact me for my resume.
chennavarri@gmail.com
- 0of 0 votes
AnswersXbox for Zombies:
- chennavarri
There are 10 zombies wating for the new Xbox in a line at a store. The store has 4 lanes, i.e. 3 waiting lanes and 1 purchase lane. The zombies are standing in the first waiting lane (ordered 1st to 10th)
All zombies have to end up in purchase lane in the same order, you can use the other waiting lanes and can move only one zombie at a time. You can talk to and move only the front zombie in any lane if you talk to any other zombie behind the first one then it will eat you. Ex: if zombies 3,6,7 are in lane 2 then you have to move zombie 3 to other lane if you want to move zombie 6.
Also, if the i'th zombie sees any zombie greater than i in the same lane then it will kill all zombies. Ex: if zombie 4 sees zombie 5 or greater in front of it in the same lane then all zombies will be killed.
And you can only move zombie's from the front of the lane, the back of the lanes are closed. So if you move zombie3 to purchase lane then only zombies 1&2 can be moved to that lane because any other zombie greater than 3 cannot stand in front of zombie3.
Think of the lanes as a stack.
In how many moves can you move all zombies into purchase lane without killing yourself and any zombies?| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - 0of 0 votes
AnswersThere are n princesses, there is one lamp inside a tower. A princess is picked randomly with repetitions and she can turn on or off the lamp. The princesses are picked infinitely. The princesses have to come up with a strategy to count the number of princesses by using the lamp information. (here lamp is a single bit, it can be on or off).
- chennavarri| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - 0of 0 votes
AnswerProblem:
- chennavarri
Given a board containing 64 squares cover it with peices of paper as small as 1 square and as big as 64 (can be of any shape but should not exceed chessboard boundaries).
If choosen a random square from the 64 squares, what is the least number of pieces of paper is required area to cover the remaining board and their shape? (you can rotate pieces of paper)
Also give a generalized solution for a board of size 2^k.| Report Duplicate | Flag | PURGE
Monitor Group Software Engineer / Developer Algorithm
I tried your code as below, and answer i got is
MaxLength:: 14 // answer should be 1 , I also tried other ones that actually fit, am I doing anything wrong?
#include <vector>
#include <iostream> // std::cout
using namespace std;
int stacking(vector<vector<int> > V){
sort(V.begin(),V.end());
vector<int> best(V.size(),1);
cout<<"Given Array:: ";
for(int ii=0;ii<V.size();++ii)
cout<<"["<<V[ii][0]<<","<<V[ii][1]<<","<<V[ii][2]<<"], ";
cout<<endl;
int ans=1;
for(int i=0;i<V.size();i++){
for(int j=0;j<i;j++){
if(V[i][0]>V[j][0] &&V[i][1]>V[j][1] && V[i][2]>V[j][2])
best[i] = max(best[i],best[j]+1);
}
ans = max(ans,best[i]);
}
return ans;
}
int main()
{
vector<int> k;
vector<vector<int> >arr;
int i1=2,i2=3,i3=4; k.clear();k.push_back(i1);k.push_back(i2);k.push_back(i3);arr.push_back(k);
i1=4,i2=3,i3=2;
k.clear();k.push_back(i1);k.push_back(i2);k.push_back(i3);arr.push_back(k);
i1=3,i2=2,i3=4;
k.clear();k.push_back(i1);k.push_back(i2);k.push_back(i3);arr.push_back(k);
cout<<"MaxLength::"<<stacking(arr);
}
//DOESNT WORK :(
hey, thought I'd try your algo, since you claim mine doesn't work (logically it should, I'll try to code when I have time)
What is exactly the input for your function? if I input the following is it valid?
int main(){
vector<int> k; vector<vector<int> >arr;
int i1=2,i2=3,i3=4;
k.push_back(i1);k.push_back(i2);k.push_back(i3);arr.push_back(k);k.clear();
i1=8,i2=2,i3=4;
k.push_back(i1);k.push_back(i2);k.push_back(i3);arr.push_back(k);k.clear();
cout<<stacking(arr);
}
So, something like a Sine wave, sorting a sine curve?
In any case, you can use any in place sorting algorithm such as QuickSort or heapsort with complexity O(nlogn) [best case]. Are we looking for better complexity?
What do you mean by "sorted list of strings"?
- chennavarri November 04, 2010Given n cuboids, compute volume for each => O(n)
sort all these cuboids based on volume => O(nlogn)
create an array to store count for each cuboid, count[n]
start from the lowest volume and check for the dimension conditions x<x',y<y',z<z'
if satisfies then increment count for that
=> O(n(n-1)/2)
Now the count array contains sum of values from 1:k, if k is the maximal path,
take max(count) O(n)
and solve k(k+1)/2 = maxVal
which gives k
total complexity:
O( n + nlogn + n(n-1)/2 + n) => O(n^2)
Vector
- chennavarri November 03, 2010Create a double out of single and traverse half of it. O(1.5n) = O(n)
- chennavarri November 03, 2010I think you got confused... the strings are not the same in this case. The sum of values is same.
100101 == 110001 in this case because number of bits set = 3 in both cases
longest common substring requires exactly same strings
There are n*(n+1)/2 intervals that can be formed using various combinations of p and q for a single array. Which means there are n*(n+1)/2 elements. Now the question is,
if K = n*(n+1)/2 can you design an algorithm that will find the max from K in less than K comparisons. Does that make sense? finding a max of an array of size K in sublinear time. How? I dont see a solution.
The best solution I can see is O(n+2+3+4+..(n-1)) => O(n*(n+1)/2) = O(n^2)
Solution:
Since, all the values are binary, all we need is count the number of bits set. So.
Count all the bits set in both arrays, totalSumA, totalSumB
when p - q == n-1, we do 1 comparison (totalSumA==totalSumB) ??
when p - q == n-2, we do 2 comparisons //just subtract the ends from totalSumA and totalSumB and compare
when p - q == n-i , we do i comparisons
=> total number of comparisons required = n*(n+1)/2
=> O(n^2)
Yes you can! LOL
-Obama
/* The question is find and delete duplicates in an array of size N with a max value N in time complexity O(N), and space O(1)
The time complexity of this program is O(2n + n +n ) = O(4n) i.e. O(n). Space complexity = O(1).
Assuming the input array can store an element of value '2n'.
From the problem we know that the elements range 1 to n so we place elements in their corresponding positions.
Pseudo code:
for each element a[i]
if(a[i]==i+1 || a[i]>n)
continue //i.e. either inplace or duplicate
else
while(true)
if(a[i]>n) //i.e. a duplicate that is already detected
break
if(a[a[i]-1]==a[i])
a[i]+=n //i.e. a duplicate is detected
break
swap a[i] and a[a[i]-1]
if(a[a[i]-1]==a[i]) //i.e. swapped inplace
break
Complexity analysis:
Consider for an element a[i], k elements are swapped. i.e. k elements are inplace.
which means each of these k elements require atmost 1 comparison i.e. O(k) and the max value k
can take is n-1 => O(n-1 + n) == O(2n) ==> O(n)
For example, element a[0], the worst case would be, doing a maximum swaps of (n-1) which
means that n-1 elements are in place. so for each of these n-1 elements we only do one comparison i.e. a[i]==i+1
Therefore, atmost 2n comparisons are made
Once we place all elements in place, all elements greater than n are duplicates,
move duplicate elements to the end, so parse once again and swap duplicates to the end.
=> Complexity = O(2n + n + n) = O(4n) ==> O(n)
Test case:
1 5 3 8 4 3 8 5 2 // i=0,
1 4 3 8 5 3 8 5 2 // i=1 swap a[1] and a[a[1]-1] i.e. swap '5' and '4'
1 8 3 4 5 3 8 5 2 // i=1 swap a[1] and a[3] i.e. swap '4' and '8',
1 5 3 4 5 3 8 8 2 // i=1 swap a[1] and a[6] i.e. swap '8' and '5',
1 14 3 4 5 3 8 8 2 // i=1 Since, a[5-1]==5 && a[1]==5, a[i]+=n => 14
1 14 3 4 5 3 8 8 2 // i=2, since a[2] = 2+1 do nothing
1 14 3 4 5 3 8 8 2 // i=3, since a[3] = 3+1 do nothing
1 14 3 4 5 3 8 8 2 // i=4, since a[4] = 4+1 do nothing
1 14 3 4 5 12 8 8 2 // i=5 Since, a[3-1]==a[i], a[i]=n+a[i] => 12
1 14 3 4 5 12 17 8 2 // i=6 Since, a[8-1]==a[i], a[i]=n+a[i] => 17
1 14 3 4 5 12 17 8 2 // i=7 Since, a[7]==8; //inplace so continue
1 2 3 4 5 12 17 8 14 // i=8 swap a[1] and a[8] i.e. swap '14' and '2'
//All duplicates are greater than n with a value a[i]-n i.e. 12,17,14 i.e. 3,8,5
*/
#include <iostream>
using namespace std;
//!Function to swap values, pass by reference
void swap(int *x,int *y){
*x = *y + *x;
*y = *x - *y;
*x = *x - *y;
cout<<"swapping '"<<*x<<"' and '"<<*y;
}
int main(){
int a[] = {3,3,3,3,3,2,2,2,2,2,2,3,3,3,3,3,2,2,2,2,2,2,4};
int n = sizeof(a)/sizeof(int);
int numComparisons = 0;
for (int i=0;i<n;++i){
++numComparisons;
if(a[i]==i+1 || a[i]>n)
continue; //i.e. either inplace or duplicate
else{
while(i<n){
++numComparisons;
if(a[i]>n) //i.e. a duplicate that is already detected
break;
int u=a[a[i]-1];
if (u==a[i])
{
a[i]+=n; //i.e. a new duplicate is detected
break;
}
cout<<endl<<"swapping a["<<i<<"] and a["<<(a[i]-1)<<"] i.e. ";swap(&a[i],&a[a[i]-1]);
if(a[a[i]-1]==a[i])
break;
}
}
}
//Move duplicates to the end, though there are two while loops,
//they break on a same condition i.e. when both pivots meet and
//pivots are ALWAYS MOVING INWARDS so the maximum number of iterations for these while loops together is N
int endPivot = sizeof(a)/sizeof(int) -1;
int beginPivot = 0;
while(beginPivot<=endPivot){
++numComparisons;
if(a[beginPivot]>n){
while(beginPivot<=endPivot){
++numComparisons;
if(a[endPivot]<n){
swap(&a[beginPivot],&a[endPivot]);
break;
}
--endPivot;
}
}
++beginPivot;
}
//Final array
cout<<endl<<"Final Array : ";
for (int k=0;k<n;++k){
cout<<a[k]<<",";
}
//Print duplicates
cout<<endl<<"Duplicates are :: ";
for (int i=beginPivot;i<n;++i){
++numComparisons;
if(a[i]>n)
cout<<a[i]-n<<",";
}
cout<<endl<<"Number of comparisons"<<numComparisons<<endl;
}
Now after landing assuming all you have is your parachute and that the other person will be alive, and no sandstorms, no unexpected and disastrous events.
A feasible algorithm:
1. after landing leave your parachute and mark your name on it.
2. keep looking around your landing location in circles increasing radius. i.e. cover a circle area of 100 meters and go back to parachute location, then cover a circle area of 200 meters and go back to parachute location. cover a circle of 300 meters and go back to parachute location.
3. If found a different parachute while searching person1 stops at that location and person2 will always come back to his parachute.
Agreed
- chennavarri October 31, 2010okay. added more info to the question.
You can only move zombie's from the front of the lane, the back of the lanes are closed. So if you move zombie3 to purchase lane then only zombies 1&2 can be moved to that lane because any other zombie greater than 3 cannot stand in front of zombie3.
Think of the lanes as a stack.
Ya, I guess kadane's algorithm gives 0 sum for negative sums. The code above is kadane's algorithm
- chennavarri October 24, 2010#include <iostream>
using namespace std;
int main()
{
int max_so_far = 0,max_ending_here =0;
int A[] = {14,-15,6,-3,2,3,4,5,-1};
int numOfLoops = 0;
int size = sizeof(A)/sizeof(int);
for(int i=0;i<size;i++){
++numOfLoops;
max_ending_here = (max_ending_here + A[i])>0?max_ending_here + A[i]:0;
max_so_far = max_ending_here>max_so_far?max_ending_here:max_so_far;
}
cout<<"number of loopings:"<<numOfLoops<<endl;
cout<<"Maximum sum::"<<max_so_far<<endl;
}
Doesn't the compiler allocate exactly 5 bytes for an A object?
- chennavarri October 22, 20101/2
- chennavarri October 22, 2010External Sort
- chennavarri October 20, 2010I guess a difficult question would be:
"How would you explain OOPs to the Pope?"
given a string, a = "a cd ef ed ca"
pivot1 points to starting of string, pivot2 points to end of string
while(pivot1<=pivot2)
if(a[pivot1]!=' ' and a[pivot2]!=' ')
if(a[pivot1]==a[pivot2])
++pivot1,--pivot2, continue loop
else
"Not a palindrome", palindromeflag = false, break;
else if(a[pivot1]==' ')
increment pivot1 and continue loop
else if(a[pivot2]==' ')
decrement pivot2 and continue loop
could you elaborate the question, max are under given rectangle? what rectangle? and how is the rectangle represented?
- chennavarri October 19, 2010Implement babylonian square root calculation method.
Complexity is O(log2(n)) but if the closest 2^k number is found in constant time then complexity is O(log2log2(n))
The code pasted below is fine but for some reason careercup's editor adds extra random semi colons. So I've pasted the code at
http://ideone.com/8nHLeH
Also, even though I used 0.000001 for stopping. the algorithm is already converged by then
/*! Implementation of Babylonian method for square root
Algorithm:
Find closest 2^k number to n
initialize xprev = 2^k
Iteratively compute 0.5*(xprev + (n/xprev) until the difference from previous is < 0.000001
//Refer to Babylonian square root calculation
* Approximated Complexity : O(1.5*log2(n) + log2log2(n)) => O(log2(n)). If the closest 2^k number is found in constant time then complexity is O(log2log2(n))
* Disclaimer: This code is ONLY implemented for understanding and demonstrating algorithm on valid inputs.
*/
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
long S = 22811111;
long tempS = S;
long X0 = 1;
float Xcurr, Xprev, diff;
int numIterations = 0;
int numBits = 0;
//Begin with an arbitrary positive starting value x0 (the closer to the root, the better).
//shift bits to find the closest 2^k to the given number
while(tempS > 0){
tempS=tempS>>1;
++numBits;
++numIterations;
}
numBits = floor(numBits/2)+1;
while(numBits > 0){
X0=X0<<1;
--numBits;++numIterations;
}
Xcurr = X0;
do{
Xprev = Xcurr;
Xcurr = .5*(Xprev + (S/Xprev));
++numIterations;
}while((Xprev-Xcurr)>0.000001);
cout<< "Square Root of "<< S<< " is "<< Xcurr<<endl;
cout<<endl<<"Complexity calculation: O(1.5*log2(n) + log2log2(n)): : "<<ceil(log2(S))+(ceil(log2(S))/2+1)+ceil(log2(log2(S)))+1<<endl;
cout<< "Number of iterations :" <<numIterations;
}
0.1666
The first question is how many times will they try to meet / go to the common point?
second, what is the travel time?
Anyways here's a hypothesis, assume travel time = 0 and number of times they travel = 1
Consider a different perspective of the problem,
given two bulbs A and B, in a 1 hr window how many times are both bulbs on? Given if a bulb goes on then it stays on for 10 minutes.
If A goes ON at t=1, both are ON if B goes ON anytime between t=1:10 and since we assumed bulb goes ON only once, for all t=11:60 it the condition fails.
So probability = 10/60 = 0.166
Any ideas? maybe conditional probability is used??
Space is exactly 2n bits for this problem.
why? because, 3 is represented as 11 in binary. if occurrences <= 3 then we need exactly 2 bits to represent the count
If we have to count more than 3 occurrences then it changes, ofcourse
No... There is no worst case for this. There's only one case. O(2n+1) = O(n)
pivot1 and pivot2 can move only forward. pivot1 cannot move beyond pivot2. At a point of time either pivot1 or pivot2 moves. in the inner loop we are not setting pivot1 to 0 every time, pivot1 only increments.
I've added the number of loopings to the code. Please check.
//!Complexity O(2n+1) = O(n).
//The code is written to demonstrate the algorithm and might fail for certain inputs
#include <iostream>
using namespace std;
int numcomputs = 0;
int main(){
int array[] = {2,3,4,5,4,1,2,3,1,1,1,2,2,4,6,2,2,4,5,1,2,3,8,8};
int S = 21, P = 384,pivot1, pivot2,size = sizeof(array)/sizeof(int);
long sum = 0, product = 0;
int minLength=size,minLenP1 = 0,minLenP2=0;
pivot1 =0; pivot2 = 0; sum = array[0]; product = array[0];
while(pivot2<size){
++pivot2;
sum = sum+array[pivot2]; product = product*array[pivot2];
++numcomputs;
while((sum>S || product>P)){ //move pivot1 if sum or product exceeded
sum=sum-array[pivot1]; product = product/array[pivot1]; ++pivot1;
++numcomputs;
if(pivot1>size) break;
}
if(sum==S && product==P && ((pivot2-pivot1) < minLength)){
if((pivot2-pivot1) < minLength){
minLength = pivot2-pivot1;
minLenP1 = pivot1,minLenP2=pivot2;
}
}
}
if(minLength==size && minLenP1==0 && minLenP2==0)
cout<<"No string found!!"<<endl;
else{
cout<<"Length of sequence: "<<minLength;
cout<<". array["<<minLenP1<<"] to array["<<minLenP2<<"]"<<endl;
for(;minLenP1<=minLenP2;++minLenP1)
cout<<array[minLenP1]<<" ,";
cout<<endl<<"size of array: "<<size<<", Total number of loopings: "<<numcomputs<<" .";
}
}
I believe it could be done in O(n) as below:
//pseudo code
pivot1 points to start of subsequence
pivot2 moves forward accumulating elements
vector sequences to store sequences that match S and P
int maxLength=size(array);
initially pivot1 = pivot2 = 0, sum = array[0], product = array[0].
while(pivot2<size)
++pivot2,
sum = sum+array[pivot2]; product = product*array[pivot2];
while((sum>S || product>P)){ //move pivot1 if sum or product exceeded
sum=sum-array[pivot1]; product = product/array[pivot1]; ++pivot1;
if(pivot1<size) break;
}
add pivot1 and pivot2 to sequences, //i.e. elements between pivot1 and pivot2 satisfy
if(pivot2-pivot1 < maxLength) maxLength = pivot2-pivot1;
pivot1 moves n and pivot2 moves n => total is 2n => O(n)
- chennavarri October 19, 2010Yep thats true.
maybe if the log2(sum) exceeds n then we just use hashing.
Ignore ants behavior, we are not concerned about area of triangle nor how ants will travel nor where or how fast they will travel. All we want to know is the probability of (consider all) ants meeting.
Assuming ant1 meeting ant2 is same as ant2 meeting ant1.
P(All ants will meet) = (number of ways all ants can meet) / (total number of possible events)
Given three ants a1,a2,a3;
The following events are possible
a. None will meet is = organizing each separately = {a1},{a2},{a3} = 1
b. Two will meet = organizing two elements together = {a1,a2},{a2,a3},{a3,a1} = 3
c. Three will meet = organizing all together = {a1,a2,a3] = 1
Probability = 1/5 = .2
Maybe I can convince the interviewer with this solution. The interviewer looks at how you are approaching rather than if you got the solution or not, thats what I believe.
- chennavarri October 18, 2010www dot optionsbender dot com/technologybending/algorithms/sublinearalgorithmforfibonacciseries
- chennavarri October 18, 2010use four more variables to count the suites. if(suite[i]!=13) then ith suite
- chennavarri October 18, 2010write a script to use grep on those 100 text files for the keyword
- chennavarri October 18, 2010sum of all face values - sum of the given deck = missing card.
Time=O(n). Space=O(1)
Undefined behavior. Output could be something like this
-1080917352,1
i.e. something,1
/*! Program to count is the sum of two numbers is equal to sum.
Assuming all positive integers
*/
#include <iostream>
#include <bitset>
using namespace std;
int givenSum = 10;
int array[] = {2,3,14,4,5,120,3,4,2,6,7,8,9,10,0,5,9,10,4,19,20,100,1,3,4,0};
int main(){
bitset<10> sumArray;
int length = sizeof(array)/sizeof(int);
for(int i=0;i<length;++i){
if((givenSum-array[i])>=0){
if(sumArray[givenSum-array[i]]==1)
cout<<"("<<array[i]<<","<<(givenSum-array[i])<<"); ";
else
sumArray[array[i]]=1;
}
}
}
Output; (6,4); (7,3); (8,2); (0,10); (5,5); (1,9); (0,10);
- chennavarri October 18, 2010How about a bitset?
Take a bitset array of size 'sum', cause we dont care about anything greater than sum
Pseudo Code
For each element i
if((sum-i)>=0)
if(bitsetArray[sum-i]==1)
return (i,(sum-i)) // a pair whose sum == sum
else
bitsetArray[i]=1;
Complexity is O(n), and space complexity is 'sum' bits
- chennavarri October 18, 2010Take a 2 bitset arrays of size n. We can use these arrays to count upto three occurrences i.e. if array1[i] = 1 and array2[i] = 1 then it means we have three occurrences of i+1 the element.
So, given an array,
for each integer 'i'
(if array2[i]==1)
array2[i] = 0,array1[i] = 1. //i.e. count is two for integer (i+1)
else
array2[i] = 1, //i.e. count is either one or three
for each element k in the arrays
if (array1[k] && array2[k])
return k //i.e. element k has count three
The advantage of having a bitset in this specific case is you can have 2n bits to store the count for n integers. Complexity is O(2n) ==> O(n), space is 2n bits.
- chennavarri October 18, 2010Alright, the question is changed to the right question.
- chennavarri October 17, 2010I assume you want to flatten something as below;
a -> b -> c -> ...
| | | ....
a1->a2.. b1->b2.. c1->c2->c3->...
when flattened
a->a1->a2->a3..an->b->b1->b2..bn->c->c1....d->d1...zn
is this what we need??
sort both arrays and add the first elements from both arrays
- chennavarri October 14, 2010336/512 ??
total number of moves that a knight can make without going out of bounds / total number of moves that a knight can make
It doesn't make sense but trying, does this work??
The first thing I got in my mind was Vista and Blue screen.. LOL
- chennavarri October 14, 2010Okay, Here's a solution. Complexity O(kLogm) i.e. finding kth element in a nxm matrix
To find the median means we have to find (n*m)/2th element in a nxm matrix. So we traverse through the matrix in ascending order. For example in the matrix below
1 3 4 6
2 5 7 8
10 11 14 17
12 15 18 20
The median is 10. This is how we traverse:
1. Take the first element of matrix add it to a min_heap.
2. Pop minimum element in the min_heap and add it to a final sorted_array.
3. For every element added to the final array
if size(sorted_array) == n/2 then break. [that is our median]
else add its right and bottom neighbors to the min_heap [dont add elements already existing]
4. Pop minimum elements until we get n/2 elements in the final sorted_array
For Example:
Final_array Min_Heap
1 [2,3]
pop 2 from Min_heap and add its bottom and right neighbors to the heap
1, 2 [3,5,10]
pop 3 and add its neighbor 4,5 ; since 5 already exists [ofcourse we need a strategy to check if the same element is already in our heap]
1, 2, 3 [4,5,10]
1,2,3,4 [5,6,7,10]
1,2,3,4,5 [6,7,10,11]
1,2,3,4,5,6 [7,8,10,11]
1,2,3,4,5,6,7 [8,10,11,14]
1,2,3,4,5,6,7,8 [10,11,14,17]
1,2,3,4,5,6,7,8,10 [11,12,14,17]
Reached n/2 elements in our Final_array so median is 10
Complexity: at any point of time our min_heap can contain atmost n+1 or m+1 elements whichever is greater so for each of the (n*m)/2 elements worst case would be logm (assuming m>n) => O((n*m)Log(m))
Just an extension to Prashanth's algorithm to improve complexity. Use a hash map for storing the locations for each alphabet <key,value> => <alphabet,arrayOfLocations>. Everytime we find an existing alphabet we insert the new location at the end of existing arrayOfLocations for that alphabet. So that when we want to access an alphabet of same type we dont have to go through the array from beginning, we can access using hash map in constant time.
Again, correct me if am wrong
//! Implementation of Babylonian method for square root
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
long S = 125348;
long tempS = S;
long X0 = 1;
float Xcurr, Xprev, diff;
int numIterations = 0;
int numBits = 0;
//Begin with an arbitrary positive starting value x0 (the closer to the root, the better).
while(tempS>0){
tempS=tempS>>1; //shift bits to find the closest 2^k to the given number
++numBits;
}
numBits = floor(numBits/2)+1;
while(numBits>0){
X0=X0<<1;
--numBits;
}
Xcurr = X0;
do{
Xprev = Xcurr;
Xcurr = .5*(Xprev + (S/Xprev));
numIterations++;
}while((Xprev-Xcurr)>0.001);
cout<< "Square Root of "<< S<< " is "<< Xcurr<<endl;
cout<< "Number of iterations :" <<numIterations;
}
Try this {10,2,3,10,2,2,2,2,4,4,4,5,5}
Your answer is '5'. Doesn't work
Alternative is using a bitset, bitset[100]. set bitset[a[i]] = 1, now we are left with elements that are not in the array. This also solves repetitions
- chennavarri October 12, 2010I would explain it using a school analogy, thats what a 10yr old kid can relate closely.
If you look at the world as a school, then all humans are in a single 'class' and each of us are an 'instance' of this class. All of us have characteristics or 'attributes' such as weight, shape, bodytype etc.. and humans have behaviors or 'methods' such as breathing, walking, thinking etc...
Now, when you look at a person playing baseball, you don't know the details how he is playing, like he/she looks at the ball, thinks something in the mind about how to hit the ball and hits it. This is basically 'encapsulating' details from others.
And as humans we are all animals and there are other animals such as tigers, elephants, monkeys, fish etc... so all tigers are in one class, elephants are in a class and so on. So all the different class of animals are 'inherited' from animal class. All animals have some similar behaviors such as talking, walking, breathing etc... each of the animal types have different forms of these behaviors. For example if a dog want to talk it barks, if a bird wants to talk it chirps and as humans we talk using sounds, so all the animals have different forms for the similar behavior which is 'polymorphism'.
Hope this helps!
well, what if the numbers are 13,12,100? I thought of a similar approach but it would complicate things more.
- chennavarri November 05, 2010