https://leetcode.com/problems/single-number/?embedable=true Description: Given a array of integers , every element appears except for one. Find that single one. non-empty nums twice 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

Too Long; Didn't Read

Get free API security automated scan in minutes

Solving the Single Number and Climbing Stairs Coding Challenge

Too Long; Didn't Read

@deft

RELATED STORIES