1
00:00:00,850 --> 00:00:03,130
Hi everyone, let's do this question.

2
00:00:03,130 --> 00:00:10,630
Given an array of integers numb's containing n plus one integers, where each integer is in the range

3
00:00:10,630 --> 00:00:12,400
one to n inclusive.

4
00:00:12,430 --> 00:00:16,870
There is only one repeated number in Numb's return this repeated number.

5
00:00:16,870 --> 00:00:23,080
You must solve the problem without modifying the array numb's and use only constant extra space.

6
00:00:23,080 --> 00:00:24,430
So this is the question over here.

7
00:00:24,430 --> 00:00:26,440
Now let's try to understand this question.

8
00:00:26,440 --> 00:00:31,750
It's given that the array numb's which is given to us has n plus one integers.

9
00:00:31,750 --> 00:00:33,220
Now let's take an example.

10
00:00:33,220 --> 00:00:34,390
Let's say this is six.

11
00:00:34,390 --> 00:00:37,900
So let's say the array which is given to us has six integers.

12
00:00:37,930 --> 00:00:39,250
Now over here it's mentioned.

13
00:00:39,250 --> 00:00:42,850
Each integer in this array is in the range one to n.

14
00:00:42,850 --> 00:00:45,790
And both of these one and n are inclusive.

15
00:00:45,790 --> 00:00:52,930
So that means the integers in the array will be 1 to 5, and both one and five will be included in the

16
00:00:52,930 --> 00:00:53,350
array.

17
00:00:53,350 --> 00:00:57,040
And over here it's mentioned there is only one repeated number in numb's.

18
00:00:57,040 --> 00:00:59,440
And we have to return this repeated number.

19
00:00:59,440 --> 00:01:00,850
So that is the question over here.

20
00:01:00,850 --> 00:01:04,990
For example, let's say the array has one, two, three, three, four and five.

21
00:01:04,990 --> 00:01:06,760
So you can see it has six numbers.

22
00:01:06,760 --> 00:01:10,180
And the numbers one, two three, four, five are there ones.

23
00:01:10,180 --> 00:01:11,980
But three is occurring two times.

24
00:01:11,980 --> 00:01:13,960
And we have to return the number three.

25
00:01:13,960 --> 00:01:15,400
So that is the question over here.

26
00:01:15,400 --> 00:01:15,730
All right.

27
00:01:15,730 --> 00:01:18,520
So we have to return the number which is being repeated.

28
00:01:18,520 --> 00:01:23,080
And the caveat is that we have to solve the problem without modifying the array.

29
00:01:23,080 --> 00:01:25,690
And we can only use extra space.

30
00:01:25,990 --> 00:01:27,250
Extra constant space.

31
00:01:27,250 --> 00:01:27,610
All right.

32
00:01:27,610 --> 00:01:30,370
So it should be O of one space complexity.

33
00:01:30,370 --> 00:01:32,380
And we cannot modify the array.

34
00:01:32,380 --> 00:01:34,180
Now over here the array is sorted.

35
00:01:34,180 --> 00:01:35,710
But this is not necessary.

36
00:01:35,710 --> 00:01:40,900
It could be something like this one then five then three then two then four.

37
00:01:40,930 --> 00:01:42,010
This is also possible.

38
00:01:42,010 --> 00:01:42,310
Right.

39
00:01:42,310 --> 00:01:46,720
And then there is one more uh number which is that 112345.

40
00:01:46,750 --> 00:01:46,990
Yeah.

41
00:01:46,990 --> 00:01:47,260
Three.

42
00:01:47,260 --> 00:01:48,190
Again three is repeating.

43
00:01:48,190 --> 00:01:48,430
Right.

44
00:01:48,430 --> 00:01:49,840
So this also could be the array.

45
00:01:49,870 --> 00:01:51,610
Now we cannot modify the array.

46
00:01:51,610 --> 00:01:53,890
So we cannot sort it or do anything like that.

47
00:01:53,890 --> 00:01:57,520
But we have to identify the repeated number and return it.

48
00:01:57,520 --> 00:01:58,750
So that's the question over here.

49
00:01:58,750 --> 00:02:02,380
Now let's go ahead and write a few test cases to understand this question.

50
00:02:02,380 --> 00:02:04,450
Now we have already looked at one test case.

51
00:02:04,450 --> 00:02:09,010
If this is the array which is given to us, we have to return the repeated number which is three.

52
00:02:09,250 --> 00:02:15,880
Now if the array has only two numbers one comma one and then one itself is the repeated number and we

53
00:02:15,880 --> 00:02:16,990
would have to return one.

54
00:02:16,990 --> 00:02:21,910
Now if the array is 132554, again we have six numbers.

55
00:02:21,910 --> 00:02:25,660
And we can see that five is being repeated and we would have to return five.

56
00:02:25,660 --> 00:02:29,080
Now again it's not necessary that these two should be together.

57
00:02:29,080 --> 00:02:34,090
It could be separate also like we can have one, five, three, two, five and four.

58
00:02:34,090 --> 00:02:38,860
Also in this case also we should be able to identify the repeating number and return it.

59
00:02:38,890 --> 00:02:39,250
All right.

60
00:02:39,250 --> 00:02:40,570
So this is the question.

61
00:02:40,570 --> 00:02:42,040
So we have understood the question.

62
00:02:42,040 --> 00:02:43,960
And we have written out a few test cases.

63
00:02:43,960 --> 00:02:47,380
In the next video let's discuss how we can solve this question.