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

Find the Celebrity

Contains Duplicate and Missing Number

2021 - HackerNoon Contributor of the Year - INNOVATION

2021 - HackerNoon Contributor of the Year - COMPUTER-SCIENCE

Solving the Single Number and Climbing Stairs Coding Challenge

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

2022 Noonies Nominee Sergei on Programming, Technology, and More

10 Ways To Effectively Sell Yourself During A Job Interview

10 Tips for Using Diagrams to Ace The System Design Interview

10 Technical Interview Tips

10 Questions for Aswin Ganesh, Noonie Nominee for Functional Programming

10 Proven Techniques to Improve Candidate Experience

2022 Noonies Nominee Sergei on Programming, Technology, and More

10 Ways To Effectively Sell Yourself During A Job Interview

10 Tips for Using Diagrams to Ace The System Design Interview

10 Technical Interview Tips

10 Questions for Aswin Ganesh, Noonie Nominee for Functional Programming

10 Proven Techniques to Improve Candidate Experience

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps