CareerCup

Can be done in O(N)

Create a Hashtable, traverse the array from o to end, if an entry does not exist, create an entry in the hashtable, if it already exists, thats the first repeated number. If we know the bounds (of the elements and not the array) we can use an array instead of a hashtable.

If extra space is allowed, hashtable is good choice

Another solution is creating binary search tree. it takes nlogn for creation. Now while inserting data we check if value is <,> or =. Node which satisfy first = condition is our first repetitive node.

any conditions for this???
random number or the value in a fixed scope?
can we use extra space?
please say it clearlly

If you can create an array to save the sorted array, then you can achiev O(NlgN).

hash table ..

Looks like the nlogn algo does not exist.
Although I did not check carefully.
http://discuss.joelonsoftware.com/default.asp?interview.11.603254.8

What about using bucket?

if can, use hashtable O(n)

if can't, use avl tree O(nlogn)

1. known array- A, use array B for storing the count of the numbers
2. B has indices from 0 to k where k is the largest element in array --O(n)
3. while incrementing count in B check if it reaching 2.
4. the index of the first occurence of 2 gives the repeated element--O(n)

ur solution is not considering the space, which also needs to be considered here .. what will happen if the array has an element 999999 etc , can we have the second array B that much size ?

Build a BST with the given array. The first repeated element can be caught while building the BST itself (if we are trying to insert a value equal to its parent). Thus just takes O(logn).

Use a fucking Hashset

'

and 1=

' and 1=

\'

'''

ookjk85h74

1 OR 1=1

1' OR '1'='1

1'1

' 1 AND 1=1

1 AND 1=1

1\'1

) or ('1'='1--

' or 1=1/*

' or 1=1--

order by 1000/*

order by 1000;--

' order by 1000/*

' order by 1000;--

' or 1=1--

" or 1=1--

') or ('a'='a

public int findFistDup(int[] a)
{
int N = a.length;
int maxA = a[0];
for (int i =0;i<N;i++)
if(a[i]>maxA) maxA = a[i];
int[] count = new int[maxA+1];
int i;
for (i=0;i<N;i++)
{
count[a[i]]++;
if(count[a[i]]>1) break;
}
return a[i];
}

import java.util.HashMap;


public class FirstRepeat {


public static void main(String args[])
{


int[] a= {10,23,44,23,44,23,12,3,18,19};
findfirstrepeated(a);





}

private static void findfirstrepeated(int[] a) {
// TODO Auto-generated method stub


HashMap<Integer,Integer> h= new HashMap<Integer,Integer>();

for(int i=0;i<a.length;i++)
{
int x=a[i];

if(h.containsKey(x))
{
h.put( x, h.get(x)+1 );

System.out.println("The first repeated is"+x );
break;

}
else
{

h.put(x, 1);
}


}


}


}

If Hash Table is used then the time complexity of the solution is O(n).
However, space complexity will also be O(n).

Else, we have to check by brute force and that solution is O(n ^ 2).

If we use sorting then also we need extra O(n) space, making the hash table far more easy than rest of the solutions.

One of the easiest ways to find the first repeated element in the array is to use an unordered set and keep inserting the element in the set until you find the repeated element which is from before present in the set, if present then return the number this will be your first repeated element.

Implementation:

#include<bits/stdc++.h>
using namespace std;
int findrepeatedelement(int arr[], int n){
unordered_set<int> s;
for(int i = 0; i < n; i++){
if(s.find(arr[i]) != s.end())
return arr[i];
else
s.insert(arr[i]);
}
}
int main(){
int arr[] = {10,23,44,23,44,23,12,3,18,19};
cout<<findrepeatedelement(arr, 10);
return 0;
}

//Bruteforce - O(n^2) Complexity.

#include<stdio.h>
#include<stdbool.h>

int main()
{

int inPt[10];
int i,j;
bool found = false;

printf("Give Input Number \n");

for(i=0;i<10;i++)
scanf("%d",&inPt[i]);

for(i=0;i<10;i++)
{
for(j=1;j<10;j++)
{
if(inPt[i]==inPt[j])
{ //for2 starts here
printf("The Repeated Number is %d", inPt[i]);
found = true;
break;
} //End of if
} // End of for2
if(found)
break;
}

return 0;

} // End of main

Okay, I think we can solve it as contruct a empty set. Now for each iteration of the input Data Structure, count if the number of elements is equal to the value of iteration. The instance the value is not equal, the element at that position is first repeated element.

can be done in O( n log n ) by first sorting inplace and then iterate through the array once checking adjacent numbers.