Solving the Single Number and Climbing Stairs Coding Challenge

Description:

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Solution:

Hello everyone. I’m not a big fan of bit operations, but sometimes they can be useful. Like in the current problem. Have you ever heard about XOR(^) operation?

You should know that 1 xor 1 will be 0

For example:

10010

XOR

01110

result

11100

Is it clear?

Bit more 11 ^ 10 = 01

Let’s use it in our current problem. We know that all numbers appear twice except one.

We can iterate over an array and eliminate elements.

Example: [1,2,3,1,2] → 1 ^ 2 ^ 1 ^ 2 = 0 and 0 ^ 3 will be 3. That is it.

public int singleNumber(int[] nums) {
    int rez = 0;
    for(int i : nums){
        rez^=i;
    }
    return rez;
}

And our next problem is

Climbing Stairs

https://leetcode.com/problems/climbing-stairs/

Description:

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.

1 step + 1 step + 1 step
1 step + 2 steps
2 steps + 1 step

Solution:

Looks like we have 2 base cases for 1 step and 2 steps. And in a 3-step stair, we have to use previous calculations. That is mean it can be a dynamic programming (DP) problem.

Usually, in DP problems we create an array or other data structure to save prev step results.

Next, we must fill it with base values. In our case we put into arr[0] = 1 (one variant for added with one stair) and arr[1] = 1 (step for 2 stairs).

And then we iterate till the n and use calculations from previous steps.

For example 1:

n = 2.

It is obvious that for 2 stairs we have 2 variants:

The first variant is to use 2 steps by one, and the second variant is to use 2 steps stride. 

The result will be 2.  dp[2] = dp[i-2] + dp[i-1] = 1 + 1 = 2;

For example 2:

n = 4.

Use results from prev example.
n = 2
The result will be 2.  dp[2] = dp[i-2] + dp[i-1] = 1 + 1 = 2;
dp[] = [1,1,2]

n = 3
dp[3] = dp[3-2] + dp[3-1] = 2 + 1 = 3;
dp[] = [1,1,2,3]

n = 4
dp[[4] = dp[4-2] + dp[4-1] = 2 + 3 = 5;
dp[] = [1,1,2,3,5]

Ok, hope it is clear. And sure let’s code it:

public int climbStairs(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

If you read it till the end, please add your reactions. It is really important for me.

Learn more on https://t.me/crack_code_interview