קאווע שטיבל

קוד: וועל אויס אלע

     public static int solution(int A, int B, int K)
        {

            if (K > B && A > 0)
                return 0;
            else
                if (K > B)//return 1 for 0 as explained below
                return 1;
            long count = 0;//we need to handle when B is 2 billion
            for (int i = B; i >= A; i--)//start of from the highest number
            {
                if (i % K == 0)//else it maybe a prime
                {

                    count = (((long)(i - A)) + K) / K; //if A is 0, add one multiple of K for 0 is divisible by all numbers. if not, still add one multiple of K for the number you’re subtracting (A). 
                    break;
                }
            }

            return (int)count;
        }

 

קוד: וועל אויס אלע

        public static int solution(int[] A)
        {

            HashSet<int> hs = new HashSet<int>();
            var B = A.OrderBy(i => i).ToArray();
            var startInd = Array.IndexOf(B, B.Where(i => i > 0).Count() > 0 ? B.First(i => i > 0) : 1);//if the array contains positive values, get the index of the first and lowest positive item

            if (startInd < 0)//if there are no positive numbers, 1 will also not be found and will set startInd to -1.
                return 1; ;


            for (int j = startInd; j < A.Length; j++)

                hs.Add(B[j]);//deals with dups


            int e = 1;
            while (hs.Contains(e))
            {
                e++;
            }
            return e;



        }

קוד: וועל אויס אלע

      public static int[] solution(string S, int[] P, int[] Q)
        {
            //Foreach character in S, we're going to add an element/tuple of 3 entries to 'prefixSums'. The elements in 'prefixSums' will indicate how many As, Cs, Gs and Ts we found in the string, 
            // with each entry in the tuple indicating a different letter, A, C and G respectively. (See later what we do about T).
            // So, for 3 of these 4 different characters, A C G and T, we have counters that we'll bump up each time we encounter one. One counter for each character. (0, 1, 2) = (A, C, G).
            // By bumping up the relevant counter for each occurrence of the letter it is associated with, they'll in the end serve as accumulators for how many times we encountered the relevant character in the string.
            // Every letter we move forward, we add a new element to 'prefixSums' and have all the counters in the new element take on (we assign to them) the values of the previous counter at their respective positions,
            // as well as adding a 1 if the letter that's associated with 'this' counter is found at the current position and a 0 if not. 
            //To answer the queries, we find out for a given S[P[K]] to S[Q[K]] the minimal factor within this boundary, by subtracting the counter at element P[K]  in 'prefixSums' 
            // [for the relevant factor/letter - i.e. starting from lowest to highest, that is index (firstIndex, second, third)] 
            // from the counter at the same position in element Q[K] in 'prefixSums', to see if we're left with a number more or equal to 1. This will tell us, that in between these two positions in S, a letter associated with the factor of this value [i.e. 1, 2, or 3] was found
            //For the forth character T (i.e. factor 4), we don't need a separate counter as we can indicate its occurrence by merely adding a new element to 'prefixSums' where all the counters remain unchanged from the previous element in 'prefixSums'.

            List<Tuple<int, int, int>> prefixSums = new List<Tuple<int, int, int>>() { Tuple.Create(0, 0, 0) };
            int[] minimalIF = new int[P.Length];




            var i = 0;
            foreach (var ch in S)

            {
                Console.WriteLine(prefixSums.Count());
                switch (ch)//here the string is traversed, and the counters are set accordingly
                {
                    case 'A':
                        prefixSums.Add(Tuple.Create(1 + prefixSums.ElementAt(i).Item1, prefixSums.ElementAt(i).Item2, prefixSums.ElementAt(i).Item3));
                        break;
                    case 'C':
                        prefixSums.Add(Tuple.Create(prefixSums.ElementAt(i).Item1, 1 + prefixSums.ElementAt(i).Item2, prefixSums.ElementAt(i).Item3));
                        break;
                    case 'G':
                        prefixSums.Add(Tuple.Create(prefixSums.ElementAt(i).Item1, prefixSums.ElementAt(i).Item2, 1 + prefixSums.ElementAt(i).Item3));
                        break;
                    default:
                        prefixSums.Add(Tuple.Create(prefixSums.ElementAt(i).Item1, prefixSums.ElementAt(i).Item2, prefixSums.ElementAt(i).Item3));

                        break;

                }
                i++;
            }

            foreach (var p in prefixSums)
                Console.WriteLine(p);

            for (int j = 0; j < P.Length; j++)//here we answer the queries
            {
                if (prefixSums.ElementAt(Q[j] + 1).Item1 - prefixSums.ElementAt(P[j]).Item1 > 0)
                    minimalIF[j] = 1;
                else if (prefixSums.ElementAt(Q[j] + 1).Item2 - prefixSums.ElementAt(P[j]).Item2 > 0)
                    minimalIF[j] = 2;
                else if (prefixSums.ElementAt(Q[j] + 1).Item3 - prefixSums.ElementAt(P[j]).Item3 > 0)
                    minimalIF[j] = 3;
                else
                    minimalIF[j] = 4;
            }
            return minimalIF;
        } 

קוד: וועל אויס אלע

//The way we do this is by first realizing that for each element in array A, you only need to check
        //all two and three sub arrays of the original array and not more (that is, for each element in array A, starting from the left, its combination with the element next to it once, and then again its combination
        //with the next element, + the element next to that one. eg. {1 2 3 4} -> (1, 2), (1,2,3), (2,3),(2,3,4), (3,4)), and keep comparing, all the while resetting 
        //the smallest subarray to the smallest found so far. 
        //The reason being that as soon as you find subarray s that contains the MA, ( minimal/smallest avg), a bigger subarray ss that includes the smaller one s will 
        //'also' contain the smallest avg (You need at least two elements as two is the minimum definition of a subarray as per the problem description.).

        //So, more concretely, take an example of a comparison of a subarray a of size 2 to a subarray b of size 3 (that also includes the subarray a of size 2), if the avg of subarray a is smaller, than the avg of subarray b - that's simple - as we can then say/know
        //two things: 1) subarray b as it is, has a higher MA than subarray a without b and hence the starting index remains in a. (All we have left to do is check which index in a causes the MA, by checking element 2 in A in combination with element 3 in A; something which we'll do anyway since we check all contiguous subarrays of 2.)
        //and 2) even if we were to add further elements to b, i.e. create a subarray c that also includes b, and their content rate of increase will be lower than the rate of increase of the number of elements reached, they'll still never cause the MA to move over from subarray a to b 
        //because the minimal avg in c will still be b, which is more than a; and out of A, a is still the minimal avg. And so on it goes..)
        //On the other hand, if b is shown to contain the MA and not a (that is, the starting index of the subarray that contains the MA is the third element in A), then we know that however more elements we would extended b to, its starting index will never move from the position it is now
        //because even if further indexes' contents cause the MA to decrease (if they cause to increase, it's simple to see that the starting index remains where it is) that can only happen because
        //of the same concept described earlier, that is, the rate of content increase [i.e. the integers/content you're getting by each added subsequent index] is smaller compared to the divisor increase [i.e. the index numbers that are constantly increasing by 1 because of extending b]
        //and so, as long this is true, the starting index cannot move. Note, if the avg of subarray of 2 is equal to avg of subarray of 3, which is certainly possible, the question specification outline that in such scenario, the starting index of the first 'minimal avg subarray' is returned and so we're good anyway.

        public static int solution(int[] A)
        {

            int[] B = new int[A.Length + 1];
            int i = 0;
            int j = 1;
            int copiedVal = A[1];
            A[1] = A[1] + A[0];
            double min = (double)A[1] / 2;
            int pos = 0;
            while (j < A.Length - 1 || (j < A.Length && i == 0))//a  refactored version of a previous solution which had n*n-1/2 run time and was done with just one While loop and a bit of trickery.
                                                                //so this still uses one while loop and knows when to change inner loop by checking if there's still 2s or 3s left in A to check.
            {
                B[i + 1] = B[i] + A[i + j];//uses prefix sums to get subarrays of 2s and 3s

                if ((double)B[i + 1] / (i + 2) < min)//calculating and comparing the MA subarrays
                {
                    min = (double)B[i + 1] / (i + 2);
                    pos = j - 1;
                }

                if (i == 1)//check for exiting the inner loop
                {
                    A[j] = copiedVal;
                    j++;
                    copiedVal = A[j];
                    A[j] = A[j] + A[(j - 1)];
                    i = -1;

                }
                i++;

            }

            return pos;
        }