2024 February 24 Problems

[daryl...@gmail.com]

Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.

Please post your solutions to this thread so others can use this as a reference.

2917Find the K-or of an Array74.3%Easy

2971Find Polygon With the Largest Perimeter66.0%Medium

3044Most Frequent Prime47.5%Medium

Please download and import the following iCalendar (.ics) files to your calendar system.

Weekly: https://us04web.zoom.us/meeting/upIqc-6upj8sGt0O2fJXTw2gC4FxRMQ-iqAT/ics?icsToken=98tyKu6uqT8tHNyRthmOR7YAB4-gKO7xiCldjbcNs03jKRhndVHxFbZkKoBSIZXZ

Join Zoom Meeting
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1

Meeting ID: 767 4768 4609
Passcode: 8wf3Qa

[Vivek H]

**************************************************************

2971Find Polygon With the Largest Perimeter66.0%Medium

***************************************************************

time complexity : O(nlogn)

class Solution {

public:

    long long largestPerimeter(vector<int>& nums) {

        int size = nums.size();

        vector<long long> sum(size, 0);

        sort(nums.begin(), nums.end());

        long long runningSum = 0;

        for(int i=0; i<size; i++) {

            runningSum += nums[i];

            sum[i] = runningSum;

        }

        long long result = -1;

        for(int i=0; i<size; i++) {

            if(i+1 < size && sum[i] > nums[i+1]) {

                result = sum[i+1];

            }

        }

        return result;

    }

};

--
whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/1d6a3ac0-7e30-427f-9522-c05deb5bcafcn%40googlegroups.com.

[Flocela Maldonado]

2971Find Polygon With the Largest Perimeter66.0%Medium

Time: O(N * logN), Memory O(1)

class Solution {

public:

long long largestPerimeter(vector<int>& nums) {

sort(nums.begin(), nums.end());

long long sumIncludingii = 0;

for (int num : nums)

{

sumIncludingii += num;

}

for (int ii=nums.size()-1; ii>=0; --ii)

{

long long longestSide = nums[ii];

long long sumOfOtherSides = sumIncludingii - nums[ii];

if (sumOfOtherSides > longestSide)

{

return sumIncludingii;

}

sumIncludingii -= nums[ii];

}

return -1;

}

};

[daryl...@gmail.com]

2971Find Polygon With the Largest Perimeter66.0%Medium

The problem pretty much tells you the algorithm for checking a polygon: check that the biggest side is smaller than all others combined. With that in mind we can just sort the sides in increasing order and walk through the array. if the current number is smaller than the current running sum of previous nums, then we can form a polygon at this point.

O(nlog(n)) time

O(n) space

func largestPerimeter(nums []int) int64 {

    var runningSum int

    ans := int64(-1)

    slices.Sort(nums)

    runningSum = nums[0] + nums[1]

    for _, num := range(nums[2:]) {

        if num < runningSum {

            ans = int64(runningSum + num)

        }

        runningSum += num

    }

    return ans

}

[Vivek H]

**********************************************************************************

3044Most Frequent Prime47.5%Medium

**********************************************************************************

class Solution {

public:

    struct comp {

        bool operator()(const pair<int, int>& p1,

                        const pair<int, int>& p2) const {

            if (p1.second == p2.second)

                return p1.first > p2.first;

            return p1.second > p2.second;

        }

    };

    bool isPrime(int num) {

        if (num <= 1) {

            return false;

        }

        for (int i = 2; i * i <= num; ++i) {

            if (num % i == 0) {

                return false;

            }

        }

        return true;

    }

    void getCoordinates(vector<vector<int>>& mat, int row, int col,

                        map<int, int>& result) {

        int R = mat.size();

        int C = mat[0].size();

        int i = row;

        int j = col;

        ;

        // east

        int S = 0;

        while (j < C) {

            S = S * 10 + mat[i][j];

            if (S > 10 && isPrime(S))

                result[S]++;

            j++;

        }

        // west

        S = 0;

        i = row;

        j = col;

        while (j >= 0) {

            S = S * 10 + mat[i][j];

            if (S > 10 && isPrime(S))

                result[S]++;

            j--;

        }

        // north

        S = 0;

        i = row;

        j = col;

        while (i >= 0) {

            S = S * 10 + mat[i][j];

            if (S > 10 && isPrime(S))

                result[S]++;

            i--;

        }

        // south

        S = 0;

        i = row;

        j = col;

        while (i < R) {

            S = S * 10 + mat[i][j];

            if (S > 10 && isPrime(S))

                result[S]++;

            i++;

        }

        // north-east

        S = 0;

        i = row;

        j = col;

        while (i >= 0 && j < C) {

            S = S * 10 + mat[i][j];

            if (S > 10 && isPrime(S))

                result[S]++;

            i--;

            j++;

        }

        // north-west

        S = 0;

        i = row;

        j = col;

        while (i >= 0 && j >= 0) {

            S = S * 10 + mat[i][j];

            if (S > 10 && isPrime(S))

                result[S]++;

            i--;

            j--;

        }

        // south-east

        S = 0;

        i = row;

        j = col;

        while (i < R && j < C) {

            S = S * 10 + mat[i][j];

            if (S > 10 && isPrime(S))

                result[S]++;

            i++;

            j++;

        }

        // south west

        S = 0;

        i = row;

        j = col;

        while (i < R && j >= 0) {

            S = S * 10 + mat[i][j];

            if (S > 10 && isPrime(S))

                result[S]++;

            i++;

            j--;

        }

    }

    void print(vector<int>& V) {

        for (auto& a : V) {

            cout << a << " ";

        }

        cout << endl;

    }

    int mostFrequentPrime(vector<vector<int>>& mat) {

        map<int, int> result;

        // dfs(mat, 0, 0, result, S);

        for (int i = 0; i < mat.size(); i++) {

            for (int j = 0; j < mat[0].size(); j++) {

                getCoordinates(mat, i, j, result);

            }

        }

        map<int, int> M;

        set<pair<int, int>, comp> S;

        for (auto& a : result) {

            cout << a.first << " " << a.second << endl;

            S.insert({a.first, a.second});

        }

        if (S.empty())

            return -1;

        return S.begin()->first;

    }

};

--

[Flocela Maldonado]

First of the Month Meeting  - Meet for coffee after!

Next meeting is the first meeting of the month- March 2, 2024!

So we'll be meeting after the zoom meeting at Peet's Coffee!

3932 Rivermark Plaza, Santa Clara, CA 95054. It's close to the library.

-Flo

[Carlos Green]

Yeah, some Peet's afterwards sounds nice

[vinay]

2917Find the K-or of an Array74.3%Easy

time: O(constant*nums.length)

space: o(1)

class Solution {

    public int findKOr(int[] nums, int k) {

        int[] bits = new int[32];

        int kor =0;

        for(int num : nums){

            int index = 0;

            while( num > 0){

                if((num&1) == 1){

                    bits[index]++;

                }

                num >>= 1;

                index++;

   

            }

        }

        for(int i = 0; i < bits.length; i++){

            if(bits[i] >= k){

                kor += Math.pow(2,i );

            }

        }

        return kor;

    }

}

--

whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/7312ccdb-d86a-4601-af72-d876afd13813n%40googlegroups.com.

[vinay]

2971Find Polygon With the Largest Perimeter66.0%Medium

Sorting gives the largest possible perimeter at the right end of the array when sides accumulate.

Test the condition given and return the perimeter.

Time O(nlogn)

Space O(1)

class Solution {

    public long largestPerimeter(int[] nums) {

        Arrays.sort(nums);

        long perimeter = 0;

        for(int num : nums){

            perimeter += num;

        }

        for(int i= nums.length-1; i >= 0; i--){

            if(perimeter-nums[i] > nums[i]){

                return perimeter;

            }

            perimeter -= nums[i];

        }

        return -1L;

    }

}

[vinay]

3044Most Frequent Prime47.5%Medium

Do as the problem asks and collect the prime count based on conditions given 

class Solution {

    int[][] dirs = null;

    Map<Integer,Integer> freqMap  = null;

    int max = -1;

    public int mostFrequentPrime(int[][] mat) {

        int rows = mat.length;

        int cols = mat[0].length;

       

        int result = -1;

        dirs = new int[][] { {-1,0},{1,0},{0,-1},{0,1},{-1,-1},{1,1},{-1,1},{1,-1}};

        freqMap = new HashMap<>();

        for(int i = 0; i < rows; i++){

            for(int j = 0; j < cols; j++){

                boolean[][] visited = new boolean[rows][cols];

                bfs(mat, visited, i,j);

            }

        }

        System.out.println(freqMap);

        for(Map.Entry<Integer,Integer> entry : freqMap.entrySet()){

            int freq = entry.getValue();

            int prime = entry.getKey();

            if(freq == max){

                result = Math.max(result, prime);

            }

        }

        return result;

       

    }

    public void bfs( int[][] mat, boolean[][] visited, int r, int c){

        int rows = mat.length;

        int cols = mat[0].length;

       

       

       

        for(int[] dir : dirs){

            int row = r;

            int col = c;

            int total = 0;

            while(row >= 0 && col >= 0 && row < rows && col < cols){

                 int num = mat[row][col];

                total = total*10 + num;

                if(total > 10 && isPrime(total)){

                    freqMap.put(total,freqMap.getOrDefault(total,0)+1);

                    max = Math.max(max, freqMap.get(total));

                }

               

                row += dir[0];

                col += dir[1];

            }

        }

           

       

    }

    public  boolean isPrime(int number) {

        if (number <= 1) {

            return false;

        }

        if (number <= 3) {

            return true;

        }

        if (number % 2 == 0 || number % 3 == 0) {

            return false;

        }

        for (int i = 5; i * i <= number; i = i + 6) {

            if (number % i == 0 || number % (i + 2) == 0) {

                return false;

            }

        }

        return true;

    }

}