CODEWITHSUNDEEP
c#arrays
John John
John John

Reputation: 1

returns the smallest positive integer (greater than 0) that does not occur in Array

I have the following question:-

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

now i tried this code:-

using System;
// you can also use other imports, for example:
// using System.Collections.Generic;

// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");

class Solution
{
    public int solution(int[] A)
    {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        int n = 1;
        Array.Sort(A);
        for (int i = 1; i <= 100000; i++)
        {
            for (int i2 = 0; i2 <= A.Length - 1; i2++)
            {
                if (A[i2] == i)

                {
                    n = A[i2] + 1;
                    break;
                }

            }



        }
        return n;

    }
}

where my code worked well for these test data:-

A = [1, 2, 3]

A = [−1, −3]

while failed for this one:-

A = [1, 3, 6, 4, 1, 2] where it return 7 instead of 5.

any advice why my code failed on the 3rd test?

Thanks

Upvotes: 0

Views: 21577

Answers (13)

Allam
Allam

Reputation: 1

  public static int Smallest(int[] A)
    {
        int maxPositiveInt = 1;
        HashSet<int> NumDic = new HashSet<int>();
        for (int i = 0; i < A.Length; i++)
        {
            if (A[i] <= 0)
            {
                continue;
            }
            if (!NumDic.Contains(A[i]))
            { 
                NumDic.Add(A[i]); 
            }
            maxPositiveInt = Math.Max(A[i], maxPositiveInt);
        }

        //All numbers are negative
        if (NumDic.Count == 0) 
         {
           return 1;
         }

        int smallestinteger = 1;
        for (int i = 0; i < A.Length; i++)
        {
            if (A[i] <= 0) 
            { 
                continue; 
            }
            if (!NumDic.Contains(smallestinteger))
            {
                return smallestinteger;
            }

            else
            {
                smallestinteger++;
            }
        }

        return maxPositiveInt + 1;
    }

Upvotes: 0

Namujiji
Namujiji

Reputation: 1

Try the below:

 public static int MinIntegerGreaterThanZeroInArray(int[] A)
    {
        int minInt;
        if (A.Length > 0)
        {
            Array.Sort(A);
            for (minInt = 1; minInt <= A.Length; minInt++)
            {
                int index = Array.BinarySearch(A, minInt);
                if (index < 0) return minInt;
            }
            return minInt;
        }
        
        //Array is empty.
        throw new InvalidOperationException();
    }

Upvotes: 0

Amr M. Abd El-Hady
Amr M. Abd El-Hady

Reputation: 1

My solution, also if someone could test how performant it is?

public int solution(int[] N) {
  if (N.Length == 0)
    return 1;
  else if (N.Length == 1)
    return N[0] >= 0 ? N[0] + 1 : 1;

  Array.Sort(N);
  int min = Array.Find(N, IsUnderZero);
  if (min ==
    default)
    return 1;
  HashSet < int > hashSet = new HashSet < int > (N);

  int max = N[N.Length - 1];
  for (int i = min + 1; i <= max + 1; i++) {
    if (!hashSet.Contains(i) && i > 0)
      return i;
  }

  return max + 1;

  bool IsUnderZero(int i) => i <= 0;
}

Upvotes: 0

React GA
React GA

Reputation: 1

static void Main(string[] args)
    {
        Console.WriteLine(solution(new int[]{1, 3, 6, 4, 1, 2}));
    }
    public static int solution(int[] A)
    {
        Array.Sort(A);
        int smallest = A[0];
        while (A.Contains(smallest+1)|| (smallest+1)<1)
        {
            smallest++;
        }
        return smallest +1;
        
    }

Upvotes: -1

Oleg Atlanov
Oleg Atlanov

Reputation: 11

The easiest one :)

class Solution
{
    public int solution(int[] array)
    {
        int[] onlyPositiveArray = array.Where(a => a > 0).OrderBy(a => a).Distinct().ToArray();

        int smallestNumber = 1;
        foreach (var number in onlyPositiveArray)
        {
            if (smallestNumber  != number)
            {
                break;
            }

            smallestNumber ++;
        }

        if (!onlyPositiveArray.Contains(smallestNumber ))
        {
            return smallestNumber;
        }
        else
        {
            return smallestNumber  + 1;
        }
    }
}

Upvotes: 1

Muhammad Rizwan
Muhammad Rizwan

Reputation: 1

 int smallestNumber=Enumerable.Range(1,(int.Parse(A.Length.ToString())+1)).Except(A).Min();
    Array.Sort(A);
    for (int number = 1; number <= 100000; number++)
    {
        for (int num = number; i2 <= A.Length - 1; num++)
        {
            if (A[num] == number)

            {
                smallestNumber = A[num] + 1;
                break;
            }

        }
    } 
    return smallestNumber; 
}

Upvotes: 0

user16266742
user16266742

Reputation: 1

class Program
{
    static void Main(string[] args)
    {
        int [] A = new int[]  {1, 2, 3};
        int n = 0;
        bool found = false;
        Array.Sort(A);
        for (int i = 1; i <= 100000; i++) {
            for (int x = 0; x <= A.Length - 1; x++) {
                int next = (x + 1) < A.Length ? (x + 1): x;
                if (A[x] > 0 && (A[next] - A[x]) > 0) {
                    n = A[x] + 1;
                    found = true;
                    break;
                }
            }

            if(found) {
                break;
            }
        }
        Console.WriteLine("Smallest number: " + n);

    }
}

Upvotes: 0

Matthew Watson
Matthew Watson

Reputation: 109712

Here's the approach that uses O(N) partitioning followed by an O(N) search. This approach does not use any additional storage, but it DOES change the contents of the array.

This code was converted from here. Also see this article.

I've added comments to try to explain how the second stage findSmallestMissing() works. I've not commented the partitioning method, since that's just a variant of a standard partition as might be used in a QuickSort algorithm.

static class Program
{
    public static void Main()
    {
        Console.WriteLine(FindSmallestMissing(1, 3, 6, 4, 1, 2));
        Console.WriteLine(FindSmallestMissing(1, 2, 3));
        Console.WriteLine(FindSmallestMissing(-1, -3));
    }

    public static int FindSmallestMissing(params int[] array)
    {
        return findSmallestMissing(array, partition(array));
    }

    // Places all the values > 0 before any values <= 0,
    // and returns the index of the first value <= 0.
    // The values are unordered.

    static int partition(int[] arr)
    {
        void swap(int x, int y)
        {
            var temp = arr[x];
            arr[x]   = arr[y];
            arr[y]   = temp;
        }

        int pIndex = 0; // Index of pivot.

        for (int i = 0; i < arr.Length; i++)
        {
            if (arr[i] > 0) // pivot is 0, hence "> 0"
                swap(i, pIndex++);
        }

        return pIndex;
    }

    // This is the clever bit.
    // We will use the +ve values in the array as flags to indicate that the number equal to that index is
    // present in the array, by making the value negative if it is found in the array.
    // This way we can store both the original number AND whether or not the number equal to that index is present
    // in a single value.
    //
    // Given n numbers that are all > 0, find the smallest missing number as follows:
    //
    // For each array index i in (0..n):
    //     val = |arr[i]| - 1;          // Subtract 1 so val will be between 0 and max +ve value in original array.
    //     if (val is in range)         // If val beyond the end of the array we can ignore it
    //     and arr[val] is non-negative // If already negative, no need to make it negative.
    //        make arr[val] negative
    //
    // After that stage, we just need to find the first positive number in the array, which indicates that
    // the number equal to that index + 1 is missing.

    // n = number of values at the start of the array that are > 0
    static int findSmallestMissing(int[] arr, int n)
    {
        for (int i = 0; i < n; i++)
        {
            int val = Math.Abs(arr[i]) - 1;

            if (val < n && arr[val] >= 0)
                arr[val] = -arr[val];
        }

        for (int i = 0; i < n; i++)
        {
            if (arr[i] > 0)   // Missing number found.
                return i + 1;
        }

        return n + 1; // No missing number found.
    }
}

Upvotes: 0

Jarkko Tirkkonen
Jarkko Tirkkonen

Reputation: 1

you can try like this.

    public static int solution(int[] A)
    {
        int smallest = -1;
        Array.Sort(A);
        if(A[0] > 1)
            return 1;
        for(int i = 0; i < A.Length; i++)
        {
          
            if(A.Length != i+1 && A[i] + 1 != A[i + 1] && A[i+1] > 0)
            {
                smallest = A[i]+1;
                break;
            }
            else if(A[i] > 0 && A.Length == i+1)
            {
                smallest = A[i] + 1;
            }
        }
        return smallest > 0 ? smallest:1;
    }

Upvotes: 0

Lasse V. Karlsen
Lasse V. Karlsen

Reputation: 391446

If you're allowed to sort the array in-place, which means modifying the input parameter value, here's a simple linear probe for the missing value (on top of the sort of course).

Here's the pseudo-code:

Sort the array
Skip all negatives and 0's at the start
Loopify the following:
    Expect 1, if not found at current location return 1
    Skip all 1's
    Expect 2, if not found at current location return 2
    Skip all 2's
    Expect 3, if not found at current location return 3
    Skip all 3's
    ... and so on for 4, 5, 6, etc. until end of array
If we get here, return currently expected value which should've been at the end

Here's the code:

public static int FirstMissingValue(int[] input)
{
    Array.Sort(input);
    
    int index = 0;
    
    // Skip negatives
    while (index < input.Length && input[index] < 1)
        index++;

    int expected = 1;
    while (index < input.Length)
    {
        if (input[index] > expected)
            return expected;
            
        // Skip number and all duplicates
        while (index < input.Length && input[index] == expected)
            index++;
            
        expected++;
    }
    
    return expected;
}

Test-cases:

Console.WriteLine(FirstMissingValue(new[] { 1, 3, 6, 4, 1, 2 }));
Console.WriteLine(FirstMissingValue(new[] { 1, 2, 3 }));
Console.WriteLine(FirstMissingValue(new[] { -1, -3 }));

output:

5
4
1

Upvotes: 3

Akshay G
Akshay G

Reputation: 2280

using System.Linq;

int smallestNumber = Enumerable.Range(1, 100000).Except(A).Min();

Upvotes: 10

julanove
julanove

Reputation: 515

Your alg won't work in case input array becomes like this: [1,2-1,1,3,5]. I did this based on your alg. Give it a try:

int[] a = new int[] { -1, -2};

        IEnumerable<int> uniqueItems = a.Distinct<int>().Where(x => x > 0);
        
        if (uniqueItems.Count() == 0)
        {
            Console.WriteLine("result: 1");
        }
        else
        {
            Array asList = uniqueItems.ToArray();
            Array.Sort(asList);

            for (int i = 1; i <= 100000; i++)
            {
                if ((int)asList.GetValue(i - 1) != i)

                {
                    Console.WriteLine("result: " + i);
                    break;
                }
            }
        }

Upvotes: 0

Tim Schmelter
Tim Schmelter

Reputation: 460208

I would use following approach that uses a HashSet<int> to check if a given integer is missing:

public static int? SmallestMissing(int[] A, int rangeStart = 1, int rangeEnd = 100_000)
{
     HashSet<int> hs = new HashSet<int>(A);
     for (int i = rangeStart; i <= rangeEnd; i++)
        if(!hs.Contains(i)) return i;
     
     return null;
}

A HashSet is a collection if unique values and it's very efficient in lookup items(complexity is O(1)). So you get a very readable and efficient algorithm at the cost of some memory.

Maybe you could optimize it by providing another algorithm in case the array is very large, you don't want to risk an OutOfMemoryException:

public static int? SmallestMissing(int[] A, int rangeStart = 1, int rangeEnd = 100_000)
{
    if(A.Length > 1_000_000)
    {
        Array.Sort(A);
        for (int i = rangeStart; i <= rangeEnd; i++)
        {
            int index = Array.BinarySearch(A, i);
            if(index < 0) return i;
        }
        return null;
    }
    
    HashSet<int> hs = new HashSet<int>(A);
    for (int i = rangeStart; i <= rangeEnd; i++)
        if(!hs.Contains(i)) return i;
 
    return null;
}

Upvotes: 4

Related Questions