FilesExpand file tree

 master

/

RepeatAndMissingNumberArray.cpp

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

72 lines (41 loc) · 1.5 KB

 master

/

RepeatAndMissingNumberArray.cpp

Top

File metadata and controls

• Code
• Blame

72 lines (41 loc) · 1.5 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/*

https://www.interviewbit.com/problems/Repeat-And-Missing-Number-Array/

You are given a read only array of n integers from 1 to n.

Each integer appears exactly once except A which appears twice and B which is missing.

Return A and B.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Note that in your output A should precede B.

Example:

Input:[3 1 2 5 3]

Output:[3, 4]

A = 3, B = 4

*/

# Approach

/*

Sum(Actual) = Sum(1...N) + A - B

Sum(Actual) - Sum(1...N) = A - B.

Sum(Actual Squares) = Sum(1^2 ... N^2) + A^2 - B^2

Sum(Actual Squares) - Sum(1^2 ... N^2) = (A - B)(A + B) = (Sum(Actual) - Sum(1...N)) ( A + B).

We can use the above 2 equations to get the value of A and B.

*/

vector<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

vector<int> res;

long long n = A.size(), x = 0, y = 0;

long long sum = (n*(n+1))/2;

long long sumSq = (n*(n+1)*(2*n+1))/6;

for(int i=0; i<n; i++)

{

sum -= (long long)A[i];

sumSq -= (long long)A[i]*(long long)A[i];

}

y = (sum + sumSq/sum)/2;

x = y-sum;

res.push_back(x); // repeat

res.push_back(y); // missing

return res;

}