CODEWITHSUNDEEP
c#arrayslistloops
Milliorn
Milliorn

Reputation: 174

How do you do this in C# without using List?

I am new to C#. The following code was a solution I came up to solve a challenge. I am unsure how to do this without using List since my understanding is that you can't push to an array in C# since they are of fixed size.

Is my understanding of what I said so far correct?

Is there a way to do this that doesn't involve creating a new array every time I need to add to an array? If there is no other way, how would I create a new array when the size of the array is unknown before my loop begins?

Return a sorted array of all non-negative numbers less than the given n which are divisible both by 3 and 4. For n = 30, the output should be

threeAndFour(n) = [0, 12, 24].

int[] threeAndFour(int n) {
  List<int> l = new List<int>(){ 0 };

  for (int i = 12; i < n; ++i)
    if (i % 12 == 0)
      l.Add(i);

  return l.ToArray();
}

EDIT: I have since refactored this code to be..

int[] threeAndFour(int n) {
  List<int> l = new List<int>(){ 0 };

  for (int i = 12; i < n; i += 12)
      l.Add(i);

  return l.ToArray();
}

Upvotes: 2

Views: 1139

Answers (6)

Dweeberly
Dweeberly

Reputation: 4777

List generally works pretty well, as I understand your question you have challenged yourself to solve a problem without using the List class. An array (or List) uses a contiguous block of memory to store elements. Arrays are of fixed size. List will dynamically expand to accept new elements but still keeps everything in a single block of memory.

You can use a linked list https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.linkedlist-1?view=netframework-4.8 to produce a simulation of an array. A linked list allocates additional memory for each element (node) that is used to point to the next (and possibly the previous). This allows you to add elements without large block allocations, but you pay a space cost (increased use of memory) for each element added. The other problem with linked lists are you can't quickly access random elements. To get to element 5, you have to go through elements 0 through 4. There's a reason arrays and array like structures are favored for many tasks, but it's always interesting to try to do common things in a different way.

Upvotes: 1

tmaj
tmaj

Reputation: 34987

A. Lists is OK

If you want to use a for to find out the numbers, then List is the appropriate data structure for collecting the numbers as you discover them.

B. Use more maths

static int[] threeAndFour(int n) {
  var a = new int[(n / 12) + 1];
  for (int i = 12; i < n; i += 12) a[i/12] = i;
  return a;
}

C. Generator pattern with IEnumerable<int>

I know that this doesn't return an array, but it does avoid a list. 

static IEnumerable<int>  threeAndFour(int n) {
  yield return 0;

  for (int i = 12; i < n; i += 12)
      yield return i;
}

D. Twist and turn to avoid a list

The code could for twice. First to figure the size or the array, and then to fill it. 

int[] threeAndFour(int n) {
  // Version: A list is really undesirable, arrays are great.
  int size = 1;
  for (int i = 12; i < n; i += 12)
      size++;
  var a = new int[size];
  a[0] = 0;
  int counter = 1;
  for (int i = 12; i < n; i += 12) a[counter++] = i;
}

Upvotes: 1

Christopher
Christopher

Reputation: 9804

I am unsure how to do this without using List since my understanding is that you can't push to an array in C# since they are of fixed size.

It is correct that arrays can not grow. List were invented as a wrapper around a array that automagically grows whenever needed. Note that you can give List a integer via the Constructor, wich will tell it the minimum size it should expect. It will allocate at least that much the first time. This can limit growth related overhead.

And dictionaries are just a variation of the list mechanics, with Hash Table key search speed.

There is only 1 other Collection I know of that can grow. However it is rarely mentioned outside of theory and some very specific cases:

Linked Lists. The linked list has a unbeatable growth performance and the lowest issue of running into OutOfMemory Exceptions due to Fragmentation. Unfortunately, their random access times are the worst as a result. Unless you can process those collections exclusively sequentally from the start (or sometimes the end), their performance will be abysmal. Only stacks and queues are likely to use them. There is however still a implementation you could use in .NET: https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.linkedlist-1

Your code holds some potential too:

  for (int i = 12; i < n; ++i)
    if (i % 12 == 0)
      l.Add(i);

It would way more effective to count up by 12 every itteration - you are only interested in every 12th number after all. You may have to change the loop, but I think a do...while would do. Also the array/minimum List size is easily predicted: Just divide n by 12 and add 1. But I asume that is mostly mock-up code and it is not actually that deterministic.

Upvotes: 1

Ian Mercer
Ian Mercer

Reputation: 39277

Since you know this goes in steps of 12 and you know how many there are before you start, you can do:

Enumerable.Range(0,n/12+1).Select(x => x*12).ToArray();

Upvotes: 1

Anu Viswan
Anu Viswan

Reputation: 18155

You could use Linq and Enumerable.Range method for the purpose. For example,

int[] threeAndFour(int n) 
{
    return Enumerable.Range(0,n).Where(x=>x%12==0).ToArray();

}

Enumerable.Range generates a sequence of integral numbers within a specified range, which is then filtered on the condition (x%12==0) to retrieve the desired result.

Upvotes: 1

Taemyr
Taemyr

Reputation: 3437

if (i % 12 == 0)

So you have figured out that the numbers which divides both 3 and 4 are precisely those numbers that divides 12.

Can you figure out how many such numbers there are below a given n? - Can you do so without counting the numbers - if so there is no need for a dynamically growing container, you can just initialize the container to the correct size.

Once you have your array just keep track of the next index to fill.

Upvotes: 1

Related Questions