Thursday, June 16, 2016

GeeksForGeeks Challenges 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<vector>
using namespace std;

int main()
{
    //code
    auto t = 0;
    std::cin >> t;

    while (t--)
    {
        auto n = 0;
        std::cin >> n;

        std::vector<int> v;
        
        while (n--)
        {
            auto x = 0;
            
            std::cin >> x;

            v.push_back(x);
        }

        auto max1 = 0;
        auto max2 = 0;
        for (size_t index = 0; index < v.size(); ++index)
        {
            if (v[index] > max1)
            {
                max2 = max1;
                max1 = v[index];
            }
            else
            {
                max2 = std::max(max2, v[index]);
            }
        }

        std::cout << (long long) max1 * max2 << std::endl;
    }
    return 0;
}


Posted by at No comments:

Tuesday, June 14, 2016

SPOJ Challenges 

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
      #include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    // your code goes here
    auto t = 0;
    std::cin >> t;
    
    for (auto c = 0; c < t; ++c)
    {
        auto s = 0, e = 0;
        std::cin >> s >> e;
 
        auto isprime = true;
        auto i = 0;
 
        for (i = s; i <= e; ++i)
        {
            if (i == 1) continue;
 
            isprime = true;
            int x = (int)std::sqrt(i);
 
            for (int f = 2; f <= x; ++f)
            {
                if (i % f == 0)
                {
                    isprime = false;
                    break;
                }
            }
 
            if (isprime)
            {
                std::cout << i << std::endl;
            }
        }
    }
    return 0;
} 
       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
      #include <iostream>
using namespace std;
 
int main() {
 // your code goes here
 auto x = 0;
 while(std::cin >> x)
 {
  if(x == 42) break;
  std::cout << x << std::endl;
 }
 return 0;
}
Posted by at No comments:

Sunday, June 5, 2016

LeetCode Challenges 

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
      /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        
        bool same = false;
        
        if((p != null) && (q != null))
        {
            bool leftTreeSame = IsSameTree(p.left, q.left);
            bool rightTreeSame = IsSameTree(p.right, q.right);
            same = leftTreeSame && rightTreeSame;            
            same = same && (p.val == q.val ? true : false);
        }

        return same;
    }
}

  • Invert Binary Tree
    • In-Place Recursive Solution (Huge improvement possible if a check for null is added before recursing root.left and root.right)
       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
      /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private void PreOrder(TreeNode root)
    {
        if (root == null) return;            
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        PreOrder(root.left);
        PreOrder(root.right);
    }

    public TreeNode InvertTree(TreeNode root)
    {
        if (root == null) return root;
        PreOrder(root);
        return root;
    }
}
    • Not In Place (Has a very bad run time performance)
       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
      /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private TreeNode minvertedroot;
    
    private void PreOrder(TreeNode root, TreeNode invertedroot)
    {
            if (root == null || invertedroot == null) return;

            TreeNode left = null;
            if (root.left != null)
            {
                left = new TreeNode(root.left.val);
            }

            TreeNode right = null;
            if (root.right != null)
            {
                right = new TreeNode(root.right.val);
            }

            invertedroot.val = root.val;
            invertedroot.left = right;
            invertedroot.right = left;

            if (root.right != null)
            {
                PreOrder(root.right, invertedroot.left);
            }

            if (root.left != null)
            {
                PreOrder(root.left, invertedroot.right);
            }

    }

    public TreeNode InvertTree(TreeNode root)
    {
        if (root == null) return root;
        minvertedroot = new TreeNode(root.val);
        PreOrder(root, minvertedroot);
        return minvertedroot;
    }
}


       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
      class Solution {
private:
    void Transpose(vector<vector<int>>& matrix)
    {
        auto rows = matrix.size();
        auto cols = rows;

        for (auto row = 0UL; row < rows; ++row)
        {
            for (auto col = row; col < cols; ++col)
            {
                std::swap(matrix[row][col], matrix[col][row]);
            }
        }
    }

    void SwapCols(vector<vector<int>>& matrix)
    {
        auto rows = matrix.size();
        auto cols = rows;

        for (auto row = 0UL; row < rows; ++row)
        {
            for (auto col = 0UL; col < cols / 2; ++col)
            {
                std::swap(matrix[row][col], matrix[row][cols - col - 1]);
            }
        }
    }

public:
    void rotate(vector<vector<int>>& matrix) {
        Transpose(matrix);
        SwapCols(matrix);
    }
};

int main()
{
    int n = 3;

    vector<vector<int>> v(n, std::vector<int>{});

    int start = 1;
    for (auto index = 0; index < n; ++index)
    {
        std::vector<int> row(n, 0);
        for (int v = 0; v < n; ++v)
        {
            row[v] = start++;
        }
        v[index].swap(row);
    }

    Solution s;
    s.rotate(v);

    for (auto const &e : v)
    {
        for (auto const &i : e)
        {
            std::cout << i << " ";
        }
        std::cout << std::endl;
    }
}

Posted by at No comments:
Subscribe to: Posts (Atom)