InterviewBit/1. Arrays/FindDuplicateinArray.cpp at master · niravnb/InterviewBit · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/*
Given a read only array of n + 1 integers between 1 and n, find one number that repeats in linear time using less than O(n) space and traversing the stream sequentially O(1) times.

Sample Input:

[3 4 1 4 1]
Sample Output:

1
If there are multiple possible answers ( like in the sample case above ), output any one.

If there is no duplicate, output -1

LINK: https://www.interviewbit.com/problems/find-duplicate-in-array/
*/


int Solution::repeatedNumber(const vector<int> &A) {
    // Do not write main() function.
    // Do not read input, instead use the arguments to the function.
    // Do not print the output, instead return values as specified
    // Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
    int n = A.size();
    vector <bool> map(n,0);
    for(int i =0; i< n; i++){
        map[A[i]] = !map[A[i]];
        if(!map[A[i]]){
            return A[i];
            break;
        }
    }

    return -1;

}


/* Sqrt(n) space
int Solution::repeatedNumber(const vector<int> &A) {
    // Do not write main() function.
    // Do not read input, instead use the arguments to the function.
    // Do not print the output, instead return values as specified
    // Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details

    int valueRange = A.size()-1;
    int range = sqrt(valueRange);

    if(range*range < valueRange)
        range++;

    int count[range+1];
    memset(count, 0, sizeof(count));

    for(int i=0;i<A.size();i++)
    {
        count[(A[i]-1)/range]++;
    }

    int repeatedRange = -1;
    int numRanges = ((valueRange-1)/range)+1;

    for(int i=0;i<numRanges && repeatedRange==-1;i++)
    {
        if(i<numRanges-1 || valueRange%range==0)
        {
            if(count[i]>range)
                repeatedRange = i;
        }
        else
        if(count[i] > valueRange%range)
            repeatedRange = i;
    }

    if(repeatedRange == -1)
        return -1;

    memset(count, 0, sizeof(count));

    for(int i=0;i<A.size();i++)
    {
        if((A[i]-1)/range == repeatedRange)
            count[(A[i]-1)%range]++;
    }

    for(int i=0;i<range;i++)
    {
        if(count[i]>1)
            return repeatedRange*range+i+1;
    }

    return -1;
}
*/