C# solution with O(n) time complexity and O(1) additional space complexity

Working on a puzzle.

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.

Below are some sample array's which are being tested.  So, in the code I have when this array  { 2, 4, 3, 5, 1 } reaches 5 I get an out of bound error which makes sense.  Any idea how to solve?
        private void Form1_Load(object sender, EventArgs e)
        {
            int[] a = new int[]{2, 3, 3, 1, 5, 2};
            a = new int[] { 2, 4, 3, 5, 1 };
            a = new int[] {1};

            //Console.Write("The first repeating elements is: ");

            Console.Write("Repeated Elements are :");
            //for (int i = 0; i < a.Length; i++)
            //{
            //    for (int j = i + 1; j < a.Length; j++)
            //    {
            //        if (a[i] == a[j])
            //            Console.Write(a[i] + " ");
            //    }
            //}

            for (int i = 0; i < a.Length; i++)
            {
                if (a[Math.Abs(a[i])] >= 0)
                {
                    a[Math.Abs(a[i])] = -a[Math.Abs(a[i])];
                    //Console.WriteLine("IF: " + a[Math.Abs(a[i])]);
                }
                else
                {
                    Console.Write(Math.Abs(a[i]) + " ");
                    break;
                }
            }         
        }

Open in new window

LVL 2
CipherISAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

 
MishaProgrammerCommented:
You have got three arrays in your code. But all these arrays have identical names "a". And you work with the last array
a = new int[] {1};

Open in new window

But this array have length 1, you only can get element
a[0]

Open in new window

But you try to get   element
a[1]

Open in new window

in row:
if (a[Math.Abs(a[i])] >= 0)

Open in new window


When you use
Math.Abs(a[i])

Open in new window

you may be can get value, which great then length of your array.
If your array have length 5, you can not get element a[5], only a[4], because numbering begins with 0 index.

May be you want something like this?
			for (int i = 0; i < a.Length; i++)
			{
				if (a[Math.Abs(a[i])-1] >= 0)
				{
					a[Math.Abs(a[i]) -1] = -a[Math.Abs(a[i]) -1];
					//Console.WriteLine("IF: " + a[Math.Abs(a[i])]);
				}
				else
				{
					Console.Write(Math.Abs(a[i]) + " ");
					break;
				}

Open in new window

1

Experts Exchange Solution brought to you by ConnectWise

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
 
CipherISAuthor Commented:
Yes, I figured that out.  Question is how to resolve the issue.  The variable "a" is assigned 3 diff times because I have 3 diff test cases.  

Any ideas how to resolve?
0
 
MishaProgrammerCommented:
Do you try code from my comment?
0
 
CipherISAuthor Commented:
Will test in a sec
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.