Interview Question Categories

FIND REPEATED AND MISSING NUMBERS IN AN ARRAY

FIND REPEATED AND MISSING NUMBERS

//you are given a sequence of ints from 1 to n in an array,
//the array would contain one repeated element, you need to find
//both the repeated and missing numbers.

namespace FindingRepeatedAndMissinginArray
{
    class Program
    {
        static int fact(int n)
        {
            if (n == 0) return 1;
            return n * fact(n - 1);
        }

        public static void FindMissingAndRepeatedNum_Method2(int[] arr)
        {
            int Sum1 = 0;
            int Sum2 = 0;

            Sum1 = (arr.Length * (arr.Length + 1)) / 2;
            Sum2 = ((2 * arr.Length + 1) * (arr.Length + 1) * arr.Length) / 6;

            for (int i = 0; i < arr.Length; i++)
            {
                Sum1 -= arr[i];
                Sum2 -= arr[i] * arr[i];
            }
            /*
                sum1 = mis-rep ------------->>1
                sum2 = mis2 - rep2 --------->>2

                sum2 = (mis+rep)(mis-rep) ----->>2

                2/1 ===>>

                sum2/sum1 = mis+rep ----------->>3


                sum2+sum12 = mis
                ----------- ---->>(3+1)
                2 * sum1


             */

            int MissingVal = (Sum2 + Sum1 * Sum1) / (2 * Sum1);
            int RepeatedVal = MissingVal - Sum1;

            Console.WriteLine(MissingVal + "    " + RepeatedVal);
        }

        public static void FindMissingAndRepeatedNum_Method1(int[] arr)
        {
            int givensum = 0;
            int givenprod = 1;

            foreach (int x in arr)
            {
                givensum = givensum + x;
                givenprod = givenprod * x;
            }

            float acctual_sum = (arr.Length * (arr.Length + 1)) / 2;
            float acctual_prod = fact(arr.Length);

            float Repeated_val = ((acctual_sum - givensum) / ((acctual_prod / givenprod) - 1));
            float Missing_val = (acctual_prod / givenprod) * Repeated_val;

            Console.WriteLine("Missing Val = " + Missing_val);
            Console.WriteLine("Repeated Val =" + Repeated_val);
        }

        static void Main(string[] args)
        {
            int[] arr = { 1, 2, 3, 3};

            FindMissingAndRepeatedNum_Method1(arr);

            FindMissingAndRepeatedNum_Method2(arr);
        }
    }
}

No comments:

Post a Comment