CODEWITHSUNDEEP
c#algorithmperformanceconsole
Monstryyy
Monstryyy

Reputation: 81

Find remaining elements in the sequence

everyone. I've this small task to do:

There are two sequences of numbers:

  1. A[0], A[1], ... , A[n].

  2. B[0], B[1], ... , B[m].

Do the following operations with the sequence A:

  1. Remove the items whose indices are divisible by B[0].

  2. In the items remained, remove those whose indices are divisible by B[1].

  3. Repeat this process up to B[m].

  4. Output the items finally remained.

Input is like this: (where -1 is delimiter for two sequences A and B)

1 2 4 3 6 5 -1 2 -1

Here goes my code (explanation done via comments):

List<int> result = new List<int>(); // list for sequence A
List<int> values = new List<int>(); // list for holding value to remove

var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
var len = Array.IndexOf(input, -1); // getting index of the first -1 (delimiter)
result = input.ToList(); // converting input array to List
result.RemoveRange(len, input.Length - len); // and deleting everything beyond first delimiter (including it) 

for (var i = len + 1; i < input.Length - 1; i++) // for the number of elements in the sequence B
{
    for (var j = 0; j < result.Count; j++) // going through all elmnts in sequence A
    {
        if (j % input[i] == 0) // if index is divisible by B[i]
        {
            values.Add(result[j]); // adding associated value to List<int> values
        }
    }
    foreach (var value in values) // after all elements in sequence A have been looked upon, now deleting those who apply to criteria
    {
        result.Remove(value);
    }
}

But the problem is that I'm only passing 5/11 tests cases. The 25% is 'Wrong result' and the rest 25% - 'Timed out'. I understand that my code is probably very badly written, but I really can't get to understand how to improve it.

So, if someone more experienced could explain (clarify) next points to me it would be very cool:

1. Am I doing parsing from the console input right? I feel like it could be done in a more elegant/efficient way.

2. Is my logic of getting value which apply to criteria and then storing them for later deleting is efficient in terms of performance? Or is there any other way to do it?

3. Why is this code not passing all test-cases or how would you change it in order to pass all of them?

Upvotes: 0

Views: 351

Answers (1)

Maras
Maras

Reputation: 982

I'm writing the answer once again, since I have misunderstood the problem completely. So undoubtly the problem in your code is a removal of elements. Let's try to avoid that. Let's try to make a new array C, where you can store all the correct numbers that should be left in the A array after each removal. So if index id is not divisible by B[i], you should add A[id] to the array C. Then, after checking all the indices with the B[i] value, you should replace the array A with the array C and do the same for B[i + 1]. Repeat until you reach the end of the array B.

The algorithm:

 1. For each value in B:
       2. For each id from 1 to length(A):
                3. If id % value != 0, add A[id] to C             
       4. A = C
 5. Return A.

EDIT: Be sure to make a new array C for each iteration of the 1. loop (or clear C after replacing A with it)

Upvotes: 1

Related Questions