Country: United States

Comment hidden because of low score. Click to expand.
1
of 5 vote

We just want to find the duplicates. We can walk on the array and put every element in the the corresponding index. If we find two elements in same position, we insert them into a set<in> as the final results.
O(1) Space, O(n) time

``````int main()
{
// 	std::vector<int> inp = {4, 2, 0, 5, 2, 0, 1} ;
std::vector<int> inp = {1, 2, 3, 0, 0, 1, 3, 6, 6,6};

//It is only for holding output
// You can print the results instead of inserting here.
std::set<int> res;
for(int i = 0; i < inp.size(); i++){
if(inp[i] == i) continue;

if(inp[inp[i]] == inp[i]) res.insert(inp[i]);
else{
auto temp = inp[inp[i]];
inp[inp[i]] = inp[i];
inp[i] = temp;
i--;
}

}
for(set<int>::iterator it = res.begin(); it != res.end(); it++)
cout << *it << " ";

return 0;
}``````

I should add that if you don't want to even reserve space for the output variable, you can print the duplicates as soon as you see them first. But in order to not print them more than once, after printing any duplicated, we can make them to -1 and be sure that we will not print them twice.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I can look at it as a kind-of directed graph, where each vertex has only one node, to another vertex. So if array is w/o dups, visually, graph will contain only circles - 1 or more.
For example array 2, 1, 3, 0, 4
contains
2 -> 3(which is a[2]) -> 0(which is a[3]) -- 2 again (circle completed)
and 1 (which is primitive circle itself) and 4 (primitive circle as well)
But when array has dups, there will be node which has two or more incoming edges. For example
2 0 3 4 2
has circle 2 -> 3 -> 4 -> 3 again, so 3 has two incoming edges - from a[0] and a[4]
what we have to do, is to run through array like it was graph and track a situation when we visited neither first (node of circle), nor new node.
Here is approx code (i use magic digits <0 not to use additional storage for nodes)

``````public List<int> getRepeated(int[] input) {
var result = new List<int>();
for(int i = 0; i < input.Length; i++) {
// this node was visited as part of other circle
if(input[i] < 0) continue;
int nextIdx = i;
var nextIdx = input[nextIdx];
// start new circle marking its head with -2
input[nextIdx] = -2;
while (true) {
if (input[nextIdx] == -2) {
input[nextIdx] = -1;
break;
} else {
// this node was already visited as a part of another circle
if(input[nextIdx] < 0) {
break;
} else {
// mark current node as visited
var current = nextIdx;
nextIdx = input[nextIdx];
input[current] = -1;
}
}
}
}
return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

@azam. not sure if your logic works. in your example array, the returned list will be 1,2,3. Whereas it should only be 2

Comment hidden because of low score. Click to expand.
0
of 0 vote

Store counts inside the array itself. For instance, you could assign values outside the prescribed value range (I chose negative numbers for convenience):

``````from numpy.random import randint
n = 13
a = randint(n, size=n)
print a

for j in a:
a[j % n] += n

for i, j in enumerate(a):
if j > n:
print i``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

@IB that is not O(1) space

Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK

It is O(1) space, you can print the results instead of putting them into a set. The set is only for holding the final results.

Comment hidden because of low score. Click to expand.
0
of 2 vote

with two passes:
1. iterate over all elements so that a[a[i]%n] = a[a[i]%n]%n + n
2. iterate a second time and if you face a[i] > n print i
note, n <= MAX_INT / 2, it's O(1) space and O(n) time, but there are two passes

it sais to do it with one pass:
1. iterate over all elements so that v=a[i], j=v%n
if a[j] < n: a[j] = a[j] + n
if n =< a[j] < 2n: a[j] = a[j] + n, print j

now n must be <= MAX_INT / 3 otherwise it won't work

Actually this O(1) space is a bit of a lie, while it is true in terms of bytes,
it uses unused bits to store occurrences.

in java:

``````public class RepeatingNumbers {
public List<Integer> findRepeat(int[] input) {
ArrayList<Integer> res = new ArrayList<>();
int n = input.length;
if(n > Integer.MAX_VALUE / 3) throw new IllegalArgumentException("input.length");
for(int i =0; i < input.length; i++) {
int j = input[i] % n;
if(input[j] < n) {
input[j] = input[j] + n;
} else if(input[j] >= n && input[j] < 2*n) {
input[j] = input[j] + n;
}
}
return res;
}

public static void main(String[] args) {
System.out.println(new RepeatingNumbers().findRepeat(new int[]{4,2,0,5,2,0,1}));
System.out.println(new RepeatingNumbers().findRepeat(new int[]{1,2,3,0,0,1,3,6,6,6}));
/*  Output
[2, 0]
[0, 1, 3, 6]
*/
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is working for me.

``````//var repAr = new int[] { 1, 2, 3, 0, 0, 1, 3, 6, 6, 6 };
var repAr = new int[] { 8, 3, 1, 7, 1, 6, 5, 6, 3 };
var repList = findRepItemsinFixedRange(repAr);
Console.WriteLine(\$"Given Items: {string.Join(",", repAr)}");
Console.WriteLine(\$"Repeated Items: {string.Join(",", repList)}");

private static HashSet<int> findRepItemsinFixedRange(int[] repAr)
{
var repList = new HashSet<int>();
for (int indx = 0; indx < repAr.Length; indx++)
{
if (repAr[valDecode(repAr[indx])] < repAr.Length)
repAr[valDecode(repAr[indx])] = valEncode(repAr[valDecode(repAr[indx])]);
else
}
for (int indx = 0; indx < repAr.Length; indx++)
repAr[indx] = valDecode(repAr[indx]);

return repList;

int valEncode(int val)
{
////abs encode - WON"T WORK FOR ZERO VALUE
//return -val;
return val + repAr.Length;
}
int valDecode(int val)
{
////abs decode - WON"T WORK FOR ZERO VALUE
//return Math.Abs(val);
if (val >= repAr.Length)
return val - repAr.Length;
return val;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

@IB, no, it will repeat already printed duplicates that's why you use a set and not a list ...
however, the approach is cool!!

``````int main()
{
std::vector<int> inp = {4, 2, 0, 5, 2, 0, 1} ;
//std::vector<int> inp = { 1, 2, 3, 0, 0, 1, 3, 6, 6 };

for (int i = 0; i < inp.size(); i++) {
if (inp[i] == i || inp[i] == -1) continue;

if (inp[inp[i]] == inp[i]) {
std::cout << inp[i] << " ";
inp[i] = -1;
} else {
std::swap(inp[inp[i]], inp[i]);
i--;
}
}
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK
In this case, I wanted to say that we can mark the duplicates by -1, and then saw your code. sounds cool.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This will do it in constant memory. We are using the source array to mark if we have visited the number before or not.

``````package algorithms;

public class FindRepeatingNums {

public static void main(String[] args) {
int[] arr = {1,3,0,2,1,4,5,3,3,0};
findRepeatingNums(arr);
}

public static void findRepeatingNums(int[] arr){
if(arr == null || arr.length <2) return;
for(int i=0; i<arr.length; i++){
if( arr[Math.abs(arr[i])] >= 0)    arr[Math.abs(arr[i])] = -1 * arr[Math.abs(arr[i])] ;
else    System.out.println(Math.abs(arr[i]));
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//requires end user to specify min and max int values allowed in nums[]
public List<Integer> findRepeat(int nums[]) {
Integer[] constantSpace = new Integer[10];  //expand to highest int allowed in nums[].
//add translation of 'zero' to 1 + nums.length/2 to support negative integers if necessary.
List<Integer> result = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
constantSpace[i] = constantSpace[i] + 1;
}
for (int i = 0; i < constantSpace.length; i++) {
if (constantSpace[i] > 1) {
}
}
return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//requirements: end user need to specify min and max int values allowed in nums[] input. ints only cost 4 bytes of memory!
//runs in 2n = O(n). Mem used = 4bytes * range of distinct ints that NEED to be found. And runs with Constant Space as requested.
public List<Integer> findRepeat(int nums[]) { // aka - ifYouGotTheMemoryIGotTheTime(int howMuchMemoryYouGot[])
int min = -9;
int max = 9;
if (nums == null) {
throw new IllegalArgumentException("input cannot be null");
}
int[] constantSpace = new int[19];
List<Integer> result = new ArrayList<Integer>();

for (int i = 0; i < nums.length; i++) {
if (nums[i] < min || nums[i] > max) {
throw new IllegalArgumentException("Invalid input: " + nums[i] + ".  int values must be >= " + min + " and <= " + max);
}
int index = nums[i] + max;
constantSpace[index] = constantSpace[index] + 1;
}

for (int i = 0; i < constantSpace.length; i++) {
if (constantSpace[i] > 1) {
}
}
return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````vector<int> FindDups(vector<int> &a)
{
vector<int> dups;
for (int i = 0; i < a.size(); ++i) {
if (a[i] != i) {
if (a[a[i]] == a[i]) {
dups.push_back(a[i]);
} else {
if (a[i] > i) {
swap(a[i], a[a[i]]);
--i;
} else {
a[a[i]] = a[i];
}
}
}
}
return dups;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Some good old python:

``````def get_dupes(nl):
"""
Sort original list in place, then
go through and compare the side by side values
Python .sort() method is O(nlogn) complexity
get_dupes is O(n)? I think :)
"""
# ex [1,1,3,4,5,5,6,6]
nl.sort()
dupes = []
for index, number in enumerate(nl):
# ex 0
current = index
# ex 1
next = index+1
# ex 0 >= 8 is false
if next >= len(nl):
break
elif nl[current] == nl[next] and number not in dupes:
# ex [1]
dupes.append(number)
# ex [1,5,6]
return dupes

get_dupes([1,5,3,6,1,5,6,4])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python 2:

``````def get_dupes(nl):
"""
Sort original list in place, then
go through and compare the side by side values
Python .sort() method is O(nlogn) complexity
get_dupes is O(n)? I think :)
"""
# ex [1,1,3,4,5,5,6,6]
nl.sort()
dupes = []
for index, number in enumerate(nl):
# ex 0
current = index
# ex 1
next = index+1
# ex 0 >= 8 is false
if next >= len(nl):
break
elif nl[current] == nl[next] and number not in dupes:
# ex [1]
dupes.append(number)
# ex [1,5,6]
return dupes

get_dupes([1,5,3,6,1,5,6,4])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why cant I Reply to a message?

Comment hidden because of low score. Click to expand.
0
of 0 vote

def findRepeat(A):
output = []
n = len(A)
for a in A:
if a < 0:
if A[a + n] < 0:
output.append(a + n)
else:
A[a + n] = A[a + n] - n
else:
if A[a] < 0:
output.append(a)
else:
A[a] = A[a] - n

return output

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def findRepeat(A):
output = []
n = len(A)
for a in A:
if a < 0:
if A[a + n] < 0:
output.append(a + n)
else:
A[a + n] = A[a + n] - n
else:
if A[a] < 0:
output.append(a)
else:
A[a] = A[a] - n

return output``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``def findRepeat(A):``

``output = []``

``n = len(A)``

``for a in A:``

``if a < 0:``

``if A[a + n] < 0:``

``output.append(a + n)``

``else:``

``A[a + n] = A[a + n] - n``

``else:``

``if A[a] < 0:``

``output.append(a)``

``else:``

``A[a] = A[a] - n``

``return output``

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def findRepeat(A):
output = []
n = len(A)
for a in A:
if a < 0:
if A[a + n] < 0:
output.append(a + n)
else:
A[a + n] = A[a + n] - n
else:
if A[a] < 0:
output.append(a)
else:
A[a] = A[a] - n

return output``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def findRepeat(A):
output = []
n = len(A)
for a in A:
if a < 0:
if A[a + n] < 0:
output.append(a + n)
else:
A[a + n] = A[a + n] - n
else:
if A[a] < 0:
output.append(a)
else:
A[a] = A[a] - n

return output``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use number as index and modify the numbers in place.

Comment hidden because of low score. Click to expand.
0
of 0 vote

How about if we sort the array and figure out if any consecutive elements are same .It is better than 0(n) i.e. nlogn

Comment hidden because of low score. Click to expand.
0
of 0 vote

Really enjoyed thinking on this problem :)
The key is that the cell values are less than n. Thus, you can use a[i] to store value i.
What I did was swapping the a[i] with the value at cell a[i] (a[a[i]]), to keep track of repetition. Here is my code:

``````set<int> Repeated(vector<int> a)
{
set<int> ret;
int i=0;
while(i<a.size())
{
if(a[i]==i) i++; // go to next element
else if(a[i] == a[a[i]]){
ret.insert(a[i]);
i++;
}
else
{
int temp = a[a[i]];
a[a[i]] = a[i];
a[i]=temp;
}
}
return ret;
}

// To execute C++, please define "int main()"
int main() {
vector<int> a = {4, 2, 0, 5, 2, 0, 1};
vector<int> b = {1, 2, 3, 0, 0, 1, 3, 6, 6,6};
set<int> c = Repeated(a);
set<int> d = Repeated(b);
for(int const & item:c)
cout<<item<<' ';
cout<<endl;
for(int const & item:d)
cout<<item<<' ';
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can use the ‘negation’ technique here, because the elements in the list are all value of 0 to n-1,
we can use the element value as the ‘index or key’ of some other meaning (by inverting the value of the index into negative).
But usually we can use the negation when the value is more than 0 (because there is no +0 or -0).
So, I’m going to modify the list value by +1. (and we should do it in one pass.) when I invert the value.
The time would be O(n) and it ends in one pass.
The code (Python) will be as follows:

``````def find_repeat(nums):
if not nums: return

for i in range(len(nums)):
index = -1
if nums[i] >= 0:
index = nums[i]
else:
index = abs(nums[i]) -1

if nums[index] >= 0:
nums[index] = -1*(nums[index] +1)
else:
# duplicates!
print(index, end=" ")

print("")

if __name__ == '__main__':
nums1 = [4, 2, 0, 5, 2, 0, 1]
nums2 = [1, 2, 3, 0, 0, 1, 3, 6, 6, 6]

find_repeat(nums1) # 0 2
find_repeat(nums2) # 0 1 3 6 6``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def findRepeats(arr):
list = [];
for i in range(len(arr)):
arr[arr[i] % len(arr)] = arr[arr[i] % len(arr)] + len(arr);
index=0;
for i in arr:
if (i/len(arr)) > 1:
list.append(index);
index=index+1;
print arr;
return list;

print findRepeats([1, 2, 2, 1, 3]);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static List<Integer> findRepeat(int[] input) {
List<Integer> list = new ArrayList<>();
int n = input.length;
int empty = n + 1;

for(int i = 0; i < input.length; i++) {
if(input[i] == i || input[i] == empty) {
continue;
} else if(input[i] == n){
} else {
int index = input[i];
int temp = input[index];

if(index < i) {
if(temp == n) {
input[i] = empty;
continue;
} else if(temp == index) {
input[index] = n;
input[i] = empty;
continue;
} else {
input[index] = input[i];
input[i] = temp;
i--;
continue;
}
} else {
if(temp == n) {
input[i] = empty;
continue;
} else if(temp == index) {
input[index] = n;
input[i] = empty;
continue;
} else {
input[index] = input[i];
input[i] = temp;
i--;
continue;
}
}

}
}return list;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static List<Integer> findRepeat(int[] input) {
List<Integer> list = new ArrayList<>();
int n = input.length;
int empty = n + 1;

for(int i = 0; i < input.length; i++) {
if(input[i] == i || input[i] == empty) {
continue;
} else if(input[i] == n){
} else {
int index = input[i];
int temp = input[index];

if(index < i) {
if(temp == n) {
input[i] = empty;
continue;
} else if(temp == index) {
input[index] = n;
input[i] = empty;
continue;
} else {
input[index] = input[i];
input[i] = temp;
i--;
continue;
}
} else {
if(temp == n) {
input[i] = empty;
continue;
} else if(temp == index) {
input[index] = n;
input[i] = empty;
continue;
} else {
input[index] = input[i];
input[i] = temp;
i--;
continue;
}
}

}
}return list;
}``````

Comment hidden because of low score. Click to expand.
-1
of 3 vote

``````public List<Integer> findRepeat(int nums[]){
List<Integer> findList = new ArrayList<Integer>();
List<Integer> findListFinal = new ArrayList<Integer>();
if(nums.length() == 0) return findListFinal;

for(int x:nums){
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 3 vote

It can be done by modifying the existing array -

Points to be noted from questions-
1- Element range in the array is 0-n-1, Hence we can use the indexes to get frequency.
2- O(1) extra space and O(n) time complexity

In our approach , we will modify the existing array to get frequency.
eg. a = [1,2,3,2] n = 4
Steps-
1- We will make the changes at index ind = a[i]%n , and will make a[ind] += n . Hence after first iteration our array will become [1,6,11,6]
2- Iterate again to get the repeated elements-
we will check if arr[i]/n > 1 => i is repeating element in the array and i can be added to resultant list, e.g. a[2]/n = 2, Hence 2 is repeating 2 times

``````public static List<Integer> repeated(int[] a){
ArrayList<Integer> list = new ArrayList<>();
int n = a.length;
for(int i=0;i<n;i++){
int ind = a[i]%n;
a[ind] = a[ind] + n;
}

for(int i=0;i<n;i++){
if(a[i]/n > 1){
}
}

return list;

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

@gator, My Logic is working fine, There is an if condition in second loop , That will add only numbers which are occurring more than 1 to the list. Kindly check again.
I have tested with few test cases.

@All , If you are down voting some answer then better give some explanation as well.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.