Find the smallest number of squared integers which sum to N

Given a positive integer n, find the smallest number of squared integers which sum to n.

For example, given n = 13, return 2 since 13 = 3² + 2² = 9 + 4.

Given n = 27, return 3 since 27 = 3² + 3² + 3² = 9 + 9 + 9.

Example:

Input:  n = 13
Output: 2  // 2*2+3*3

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int minPerfectSquareSumN(int num)
{
    int dp[num + 1];

    if (num == 1)
        return 1;
    for (int i = 0; i <= num; i++)
    {
        dp[i] = i;
        for (int j = 1; j * j <= i; j++)
        {
            dp[i] = min(dp[i], 1 + dp[i - j * j]);
        }
    }
    return dp[num];
}
int main()
{
    int num = 13;

    cout << minPerfectSquareSumN(num) << "\n";

    return 0;
}

Number of ways to move from top left corner to bottom right corner

You are given an N by M matrix of 0s and 1s. Starting from the top left corner, how many ways are there to reach the bottom right corner?

You can only move right and down. 0 represents an empty space while 1 represents a wall you cannot walk through.

For example, given the following matrix:

[[0, 0, 1],
 [0, 0, 1],
 [1, 0, 0]]

Return two, as there are only two ways to get to the bottom right:

• Right, down, down, right
• Down, right, down, right

The top left corner and bottom right corner will always be 0

Example:

Input:  matrix = {{0, 0, 1}, {0, 0, 1}, {1, 0, 0}}
Output: 2

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int numberOfWays(vector<vector<int>> &matrix)
{
    int n = matrix.size();
    if (n == 0)
        return 0;
    int m = matrix[0].size();
    int dp[n][m];
    for (int i = 0; i < n; i++)
    {
        if (matrix[i][0] == 1)
        {
            while (i < n)
            {
                dp[i][0] = 0;
                i++;
            }
        }
        else
            dp[i][0] = 1;
    }
    for (int i = 0; i < m; i++)
    {
        if (matrix[0][i] == 1)
        {
            while (i < m)
            {
                dp[0][i] = 0;
                i++;
            }
        }
        else
            dp[0][i] = 1;
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            if (matrix[i][j] == 1)
                dp[i][j] = 0;
            else
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[n - 1][m - 1];
}
int main()
{

    vector<vector<int>> matrix = {{0, 0, 1},
                                  {0, 0, 1},
                                  {1, 0, 0}};

    cout << numberOfWays(matrix) << "\n";

    return 0;
}

Inverted cells

You are given a matrix $n\ast m$. The matrix rows are numbered from $1$ to $n$ from top to bottom and the matrix columns are numbered from $1$ to $m$ from left to right. The cells of the field at the intersection of the $x^{th}$ row and the $y^{th}$column has coordinates $(x,y)$.

Every cell is empty or blocked. For every cell $(x,y)$, determine if you change the state of cell $(x,y)$(empty to blocked or blocked to empty), then is it possible to reach cell $(n,m)$ from $(1,1)$ by going only down and right.

Input format

Example:

Input : 
5 5
..#..
#...#
#...#
....#
.##..
Output:
0 0 1 1 1 
1 0 1 1 1 
1 1 1 1 1 
1 1 1 0 1 
1 1 1 0 0 

Approach

Java

import java.io.BufferedReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class InvertedCells {
    static int n, m;
    static char[][] g;
    static boolean[][] art, dp1, dp2;
    static int time = 0;
    static int rooti = 0, rootj = 0;
    static int rootChildren = 0;
    static int[][] start, low, state;
    static int[][] parent;

    public static void main(String[] args) {
        n = 5;
        m = 5;

        char arr[][] = { { '.', '.', '#', '.', '.' }, { '#', '.', '.', '.', '#' }, { '#', '.', '.', '.', '#' },
                { '.', '.', '.', '.', '#' }, { '.', '#', '#', '.', '.' } };

        g = new char[n][m];
        for (int i = 0; i < n; i++) {
            g[i] = arr[i];
        }

        dp1 = new boolean[n][m];
        dp1[0][0] = true;

        dp2 = new boolean[n][m];
        dp2[n - 1][m - 1] = true;

        art = new boolean[n][m];

        int[][] next = { { 0, 1 }, { 1, 0 } };
        int[][] prev = { { 0, -1 }, { -1, 0 } };

        dp1(next, dp1);
        dp2(prev, dp2);

        if (!dp1[n - 1][m - 1]) {
            // not reachable
            for (int i = 0; i < n; i++) {
                Arrays.fill(art[i], true);
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (g[i][j] == '.')
                        continue;
                    for (int a = 0; a < 2; a++) {
                        for (int b = 0; b < 2; b++) {
                            int previ = i + prev[a][0];
                            int prevj = j + prev[a][1];
                            int nexti = i + next[b][0];
                            int nextj = j + next[b][1];
                            if (nexti >= n || nextj >= m || nexti < 0 || nextj < 0)
                                continue;
                            if (previ >= n || prevj >= m || previ < 0 || prevj < 0)
                                continue;
                            if (dp1[previ][prevj] && dp2[nexti][nextj])
                                art[i][j] = false;
                        }
                    }
                }
            }
        } else {
            // reachable do articulation point algorithm
            start = new int[n][m];
            low = new int[n][m];
            state = new int[n][m];
            art = new boolean[n][m];
            parent = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (state[i][j] == 0 && dp1[i][j] && dp2[i][j]) {
                        rooti = i;
                        rootj = j;
                        dfs(i, j);
                        art[i][j] = rootChildren > 1;
                    }
                }
            }
            art[0][0] = true;
            art[n - 1][m - 1] = true;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (art[i][j])
                    sb.append("0");
                else
                    sb.append("1");

                if (j != m - 1)
                    sb.append(" ");
            }
            sb.append("\n");
        }

        System.out.print(sb);

    }

    public static void dp1(int[][] dir, boolean[][] dp) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!dp[i][j])
                    continue;
                if (g[i][j] == '#') {
                    dp[i][j] = false;
                    continue;
                }
                for (int k = 0; k < dir.length; k++) {
                    int[] d = dir[k];
                    int newi = i + d[0];
                    int newj = j + d[1];
                    if (newi >= n || newj >= m || newi < 0 || newj < 0)
                        continue;
                    dp[newi][newj] = true;
                }
            }
        }
    }

    public static void dp2(int[][] dir, boolean[][] dp) {
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                if (!dp[i][j])
                    continue;
                if (g[i][j] == '#') {
                    dp[i][j] = false;
                    continue;
                }
                for (int k = 0; k < dir.length; k++) {
                    int[] d = dir[k];
                    int newi = i + d[0];
                    int newj = j + d[1];
                    if (newi >= n || newj >= m || newi < 0 || newj < 0)
                        continue;
                    dp[newi][newj] = true;
                }
            }
        }
    }

    public static void dfs(int i, int j) {
        time++;
        start[i][j] = low[i][j] = time;
        state[i][j] = 1;

        int[][] dir = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

        for (int a = 0; a < dir.length; a++) {
            int newi = i + dir[a][0];
            int newj = j + dir[a][1];
            if (newi >= n || newj >= m || newi < 0 || newj < 0)
                continue;
            if (!(dp1[newi][newj] && dp2[newi][newj]))
                continue;
            if (state[newi][newj] == 0) {
                if (i == rooti && j == rootj)
                    rootChildren++;
                parent[newi][newj] = i * 1002 + n;
                dfs(newi, newj);
                if (low[newi][newj] >= start[i][j])
                    art[i][j] = true;
                low[i][j] = Math.min(low[i][j], low[newi][newj]);
            } else if (newi * 1002 + newj != parent[i][j])
                low[i][j] = Math.min(low[i][j], low[newi][newj]);
        }

        state[i][j] = 2;
        time++;
    }

    // print the matrix
    public static void print(int[][] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[0].length; j++)
                System.out.print(a[i][j] + " ");
            System.out.println("");
        }
        System.out.println("");
    }

}