In flight entertainment solution

InFlightEntertainment

    using System;
    using System.Collections.Generic;
    
    namespace InFlightEntertainment
    {
        public class Program
        {
            public static void Main(string[] args)
            {
                test("2", "Yes", areTwoMoviesPresentForFlight(60, new int[]{5, 15, 20, 17, 40, 20}));
                
                // Version 1 
                Console.WriteLine("Version 1");
                test("any", "Yes", areAnyMoviesPresentForFlight(60, new int[]{5, 10, 23, 45}));
                test("any", "No", areAnyMoviesPresentForFlight(60, new int[]{5, 15, 23, 16}));
                test("any", "Yes", areAnyMoviesPresentForFlight(5, new int[]{ 5 }));
                test("any", "Yes", areAnyMoviesPresentForFlight(60, new int[]{75, 10, 20, 40 }));
                
                // Version 2
                Console.WriteLine("Version 2");
                test("any", "Yes", areAnyMoviesPresentForFlight2(60, new int[]{5, 10, 23, 45}));
                test("any", "No", areAnyMoviesPresentForFlight2(60, new int[]{5, 15, 23, 16}));
                test("any", "Yes", areAnyMoviesPresentForFlight2(5, new int[]{ 5 }));
                test("any", "Yes", areAnyMoviesPresentForFlight2(60, new int[]{75, 10, 20, 40 }));
            }
            
            static void test(string n, string expected, bool result) {
                Console.WriteLine("Are there {0} movies? Expected: {1}, Actual: {2}", n, expected, result ? "Yes" : "No");
            }
            
            // Version 1: 
            // Time complexity: O(n^2)
            // Space complexity: O(n)
            static bool areAnyMoviesPresentForFlight(int flight_length, int[] movie_lengths) {
                 	
                HashSet<int> movieHash = new HashSet<int>(movie_lengths);
                int remaining_movie_length = flight_length;
                
                for (int i = 0; i < movie_lengths.Length; i++) {
                    remaining_movie_length -= movie_lengths[i];
                    if (remaining_movie_length == 0 || movieHash.Contains(remaining_movie_length)) {
                        return true;
                    }
                    
                    int movie_length_so_far = movie_lengths[i];
                    
                    for (int j = i + 1; j < movie_lengths.Length; j++) {            
                        movie_length_so_far += movie_lengths[j];
                        if (movie_length_so_far == flight_length) {
                            return true;
                        }
                    }
                    
                }
                     
                return false;
        	}
            
            // Version 2
            // Time Complexity: O(nlogn)
            // Spae complexity: O(1)
            static bool areAnyMoviesPresentForFlight2(int flight_length, int[] movie_lengths) {
                if (movie_lengths.Length == 0) {
                    return false;
                }
                
                // Sort items in  descending order
                Array.Sort<int>(movie_lengths, new Comparison<int>(
                    (i1, i2) => i2.CompareTo(i1)
                ));
                
                int remaining_movie_length = flight_length;
                foreach (var current_movie_length in movie_lengths) {
                    if (remaining_movie_length < current_movie_length) {
                        continue;
                    } else if (remaining_movie_length == current_movie_length) {
                        return true;
                    } else {
                        remaining_movie_length -= current_movie_length;
                    }                 
                }
                
                return remaining_movie_length == 0;
            }
            
            static bool areTwoMoviesPresentForFlight(int flight_length, int[] movie_lengths) {
                HashSet<int> movieHash = new HashSet<int>();
                
                foreach (var first_movie_length in movie_lengths) {
                    var second_movie_length = flight_length - first_movie_length;
                    if (movieHash.Contains(second_movie_length)) {
                        return true;
                    }
                    
                    movieHash.Add(first_movie_length);
                }
      
                return false;
        	}
        }
    }