when u xor nos with odd number of times we will get back the same no.only
even occurences will give 0.question is to find the no with even
occurence.how will you find that no?
On Tue, Aug 16, 2011 at 1:41 PM, MAC macatad...@gmail.com wrote:
Given an array of integers. Each number in the array
Given an array of integers. Each number in the array repeats ODD number of
times, but only 1 number repeated for EVEN number of times. Find that
number.
--
thanks
--mac
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
One easier thing would be to use a map to solve this.
On Tue, Aug 16, 2011 at 1:41 PM, MAC macatad...@gmail.com wrote:
Given an array of integers. Each number in the array repeats ODD number of
times, but only 1 number repeated for EVEN number of times. Find that
number.
--
thanks
@sukran:
If you were asking for the map based solution
space and time complexity would be o(n).
On Tue, Aug 16, 2011 at 2:34 PM, sukran dhawan sukrandha...@gmail.comwrote:
what is the complexity in which it has been done ?
On Tue, Aug 16, 2011 at 1:41 PM, MAC macatad...@gmail.com wrote:
The question needed o(1) space and o(n) time ... o(n) map approach is
obviously fine but space is taken up ...
On Tue, Aug 16, 2011 at 2:38 PM, Raghavan its...@gmail.com wrote:
@sukran:
If you were asking for the map based solution
space and time complexity would be o(n).
On Tue, Aug
- Sort the array - o(log n) based on the sorting strategy might be radix
sort
- check the numbers count have a counter o(1) space and again o(n) time
- changing from one number to other check counter%2 == 0 if so then we
get answer
So consolidated time would be o(n) and space is
i think XOR operator should be used to solve question.
Given the integers in the array A: n1,n2...nk,
we can do this recursively:
XOR all the integers in A, assume the result is F = n1^n2^...^nk,
F must not be 0.
for i-th bit in F from rightmost to left most:
if the i-th bit is 1, halve A
given two arrays : with all distinct elements but one element in common.
Find the common element in optimal time.
--
*MOHIT VERMA*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
meaning ? what is a common element ? example ???
On Sun, Aug 14, 2011 at 6:37 PM, mohit verma mohit89m...@gmail.com wrote:
given two arrays : with all distinct elements but one element in common.
Find the common element in optimal time.
--
example:
array 1 :: 1 2 3 4 5 6 7 8 9 10 15
array 2:: 23 34 56 13 15 57 432 348
On Sun, Aug 14, 2011 at 6:44 PM, shady sinv...@gmail.com wrote:
meaning ? what is a common element ? example ???
On Sun, Aug 14, 2011 at 6:37 PM, mohit verma mohit89m...@gmail.comwrote:
how about binary search of each element from array 1 on array 2?
overall complexity : O(nlogn)
On 14 August 2011 18:46, mohit verma mohit89m...@gmail.com wrote:
example:
array 1 :: 1 2 3 4 5 6 7 8 9 10 15
array 2:: 23 34 56 13 15 57 432 348
On Sun, Aug 14, 2011 at 6:44 PM, shady
Hashing
O(n+m)
On Sun, Aug 14, 2011 at 6:48 PM, Dipankar Patro dip10c...@gmail.com wrote:
how about binary search of each element from array 1 on array 2?
overall complexity : O(nlogn)
On 14 August 2011 18:46, mohit verma mohit89m...@gmail.com wrote:
example:
array 1 :: 1 2 3 4 5 6 7 8
@ Sagar:
What if extra space in not allowed?
I think then we have to use the binary search method...
On 14 August 2011 18:50, sagar pareek sagarpar...@gmail.com wrote:
Hashing
O(n+m)
On Sun, Aug 14, 2011 at 6:48 PM, Dipankar Patro dip10c...@gmail.comwrote:
how about binary search of each
@sagar suppose numbers are very large( 10^9) , how will you hash then ?
can you please state the hashing function in this case
On Sun, Aug 14, 2011 at 6:50 PM, sagar pareek sagarpar...@gmail.com wrote:
Hashing
O(n+m)
On Sun, Aug 14, 2011 at 6:48 PM, Dipankar Patro dip10c...@gmail.comwrote:
i feel binary search idea is the best
guys i am having problem in finding out complexity...here is my
solution to the above problem...whats the complexity...
sort the 2 arraysa and b
l=0,i=0,flag=0;
while(a[i]b[0]) // to start comparing from the value that is
slightly greater than the
doesnt matter Order will be (nlogn)
where n is max(elements in first set, elements in 2nd set)
PS : dont submit codes from next time
On Sun, Aug 14, 2011 at 7:43 PM, Nikhil Veliath nve...@gmail.com wrote:
i feel binary search idea is the best
guys i am having problem in finding out
An array of strings is given and you have to find out whether a circular
chain with all character can be formed or not?
Circular chain is formed in way that: if last char of a string is equal to
first char of another string then it can be joined.:
like ab bxc === axbbxc
maintain an array indexed on alphabets 'a' to 'z'.
now count the occurence of each character taking *last character* of each
string
{asdsb,csasaa, bc, bc}
in this case
arr[a]=1;
arr[b]=1;
arr[c]=2;
now start with each sting let first character be first and last character be
last
while
why following?
if(first==last)
return false;
example:
axxa, ayyb, bzza === ayybbzzaaxxa
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
see the following example:
*a*kdhd*a* ,*b*hdgd*c*, *c*hdjd*b*
On Sat, Aug 13, 2011 at 10:20 PM, Yasir yasir@gmail.com wrote:
why following?
if(first==last)
return false;
example:
axxa, ayyb, bzza === ayybbzzaaxxa
--
You received this message because you are subscribed to the
i got error,my sol will not work for all cases
On Sat, Aug 13, 2011 at 10:22 PM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
see the following example:
*a*kdhd*a* ,*b*hdgd*c*, *c*hdjd*b*
On Sat, Aug 13, 2011 at 10:20 PM, Yasir yasir@gmail.com wrote:
why following?
if(first==last)
Maybe you are looking for this:http://www.codechef.com/problems/WORDS1
On Sat, Aug 13, 2011 at 10:25 PM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
i got error,my sol will not work for all cases
On Sat, Aug 13, 2011 at 10:22 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
see the
Given an array of integers, for each element of the array, print the
first number on the right side of the element which is smaller than
it. print -1 is there is no such element.
eg: 3,4,2,18,19,1,10
Ans: 2,2,1,10,10,-1,-1
O(n^2) solution is trivial.
One solution could be:
Insert the elements
Use stack
On Tue, Jul 26, 2011 at 5:22 PM, Shikhar shikharko...@gmail.com wrote:
Given an array of integers, for each element of the array, print the
first number on the right side of the element which is smaller than
it. print -1 is there is no such element.
eg: 3,4,2,18,19,1,10
Ans:
Sorry for the above mistakeits not O(n)
On Tue, Jul 26, 2011 at 5:29 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote:
Use stack
On Tue, Jul 26, 2011 at 5:22 PM, Shikhar shikharko...@gmail.com wrote:
Given an array of integers, for each element of the array, print the
first number on
The O/P of ur example should be 2,2,1,1,1,-1,-1
or am I getting it wrong ??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
We have three arrays
A=[a1,a2,...an]
B=[b1,b2,...bn]
C=[c1,c2,...cn]
Write a method which takes these three arrays as input and return true
if there is a combination [ai,bj,ck] such that ai+bj+ck = 0.
O(n^3) solution is obvious. The questions is can we do better than
this?
Thanks
i have a n^2logn solution
sort the third array,.. then for every pair in a and b search for the number
which makes the sum zero using binary search
but guess a better soln must exist
On Thu, Feb 17, 2011 at 11:38 PM, bittu shashank7andr...@gmail.com wrote:
We have three arrays
Here are two methods to do in O(n^2)
1) Insert elements of first array in hash and then for every pair of
elements in (Bj, Ck) find if -(Bj + Ck) is in hash
2) Without extra space:
sort arrays A and B
now for each element in Ck find a pair (Ai, Bj) which sums to -Ck as below
let p1 point to
I think you can use heap.
Thanks,
Sathaiah
On Wed, Jul 21, 2010 at 12:06 PM, divya sweetdivya@gmail.com wrote:
Given an array A of N elements, where N approaches infinity, there are
S elements in it where SN. WAP to insert an element at A[S] if it
does not exist in A[0S-1].
--
You
Given an array A of N elements, where N approaches infinity, there are
S elements in it where SN. WAP to insert an element at A[S] if it
does not exist in A[0S-1].
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
@sharad
while storing each element in hash by your approach u ll check if its
already there in hash. so the complexity here will be O(n2). correct me if i
m wrong. isnt there ny better algo..?
On 6 June 2010 06:28, sharad kumar aryansmit3...@gmail.com wrote:
@dhivya:keep storing the first
No it will be O(n).
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Google Groups
Algorithm
#includeiostream
#includemap
#includeiterator
using namespace std;
int main()
{
int arr[5]={12,3,4,3,3};
mapint,intmp;
int i=0;
for(i=0;i5;++i)
{
if(!(mp[arr[i]]))
mp[arr[i]]=i;
else
continue;
Given an array with some repeating numbers. Like 12,6,5,12,6
output: 12,12,6,6,5
12 shud come before 6 since it is earlier in list. So cant use a
dictionary.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
35 matches
Mail list logo