Farthest Co-prime


  • 0
    P

    Given an array of n numbers, replace each element with it’s farthest coprime in the range [2, 250]. Example, the farthest coprime for 2 is 249 and for 243 is 2.


  • 1
    T
    class solution
        {                
            public int farthestprime(int num)
            {
                bool[] flag = new bool[251];
                for (int i = 2; i <= num; ++i)
                {
                    if (num % i == 0)
                    {
                        flag[i] = true;
                        for (int j = 2; j * i <= 250; ++j)
                        {
                            flag[i * j] = true;
                        }
                    }
                }
                int front = 2;
                while(front<=250&&flag[front]==true){
                    front++;
                }
                int back=250;
                while(back>=0&&flag[back]==true){
                    back--;
                }
                return (num-front)>(back-num)?front:back;
            }
        }
    

  • 1

    @tianjiao and then you'll invoke this method for each element in the input array?


  • 0
    D
            static void Main(string[] args)
            {
                var coPrimeStart = 2;
                var coPrimeEnd = 250;
                var list = new int[coPrimeEnd];
    
                Console.WriteLine(Coprime(2, 249));
    
                for (var i = coPrimeStart; i <= coPrimeEnd; i++)
                {
                    list[i - 1] = GetFarthestCoPrime(i, coPrimeStart, coPrimeEnd);
                }
            }
    
            public static int GetFarthestCoPrime(int number, int start, int end)
            {
                var leftMost = 0;
                var rightMost = 0;
    
                for (var i = start; i <= end; i++)
                {
                    if (Coprime(i, number))
                    {
                        if (0 == leftMost)
                        {
                            leftMost = i;
                        }
    
                        rightMost = i;
                    }
                }
    
                if (rightMost - number > Math.Abs(leftMost - number))
                {
                    return rightMost;
                }
    
                return leftMost;
            }
    
            public static int GetGCDByModulus(int value1, int value2)
            {
                while (value1 != 0 && value2 != 0)
                {
                    if (value1 > value2)
                        value1 %= value2;
                    else
                        value2 %= value1;
                }
                return Math.Max(value1, value2);
            }
    
            public static bool Coprime(int value1, int value2)
            {
                return GetGCDByModulus(value1, value2) == 1;
            }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.