CSES Introduction problem set’s answers

Weird Algorithm

Problem statement

1. The goal is to reach 1 when given a positive int n and output all numbers along the way.
2. The algo to reach 1 is
   • if n is even divide by 2
   • if n is odd multiply by 2 and add 1

E.g. n = 3, output = 3 —> 10 —> 5 —> 16 —> 8 —> —> 4 —> 2 —> 1

Intuition

This is quite a simple problem, we could easily use regular multiplication and division to solve this, we can also use bitwise operators. For those who aren’t familiar with bitwise operators, there are the following operators we will for this problem.

1. Left shift << n multiplies a number by 2, n times
2. Right shift >> n dividies number by 2, n times
3. Bitwise and x & y. If the bit values of both x and y are 1, then the output is 1 else 0.

int x = 0b10;
int y = 0b1;
int z = x & y; // z = 0;

Code

int main()
{
    setIO();
 
    unsigned long long int n, a;
    cin >> n;
 
    cout << n << " ";
 
    while (n != 0b1) // Run until n is not 1
    {
        if (n == 0)
            break;
        if (n & 0b1) // Check if last bit is a 1. => Odd number
        {
            a = n; // Keep a copy of n
            n <<= 1; // Multiply by 2
            n += a + 1; // Add it n (a) one more to multiply by 3 and add 1
        }
        else
        {
            n >>= 1; // Divide by 2 once if n is even
        }
        cout << n << " ";
    }
}
 

Missing Number

Problem statement

1. Input 1: Given a number n
2. Input 2: All numbers from 1 to n except one number
3. We need to find that number

Intuition

Approach 1:

1. Get all numbers and sort them
2. Iterate through sorted numbers. If any number + 1 isn’t equal to the next number, number + 1 is the answer

Approach 2:

1. This is a mathematical approach.
2. Sum of n numbers is: n * (n + 1) / 2.
3. When we get inputs from file one by one we subtract it from the sum.
4. The sum we are left at the end is the answer.

Code

Approach 1: Sort and Iterate

int main()
{
    unsigned int n, a;
    vector<unsigned int> v;
    cin >> n;
 
    while (cin >> a)
        v.push_back(a);
    sort(v.begin(), v.end());
    if (v[0] != 1)
        cout << 1;
    else
    {
 
        for (unsigned int i = 0; i < v.size(); i++)
        {
            if (v[i] + 1 != v[i + 1])
            {
                cout << v[i] + 1;
                break;
            }
        }
    }
 

Approach 2: Sum n numbers and subtract inputs

int main()
{
    unsigned long long n, a;
    cin >> n;
    unsigned long long sum;
    sum = n * (n + 1);
    sum >>= 1;
 
    while (cin >> a)
    {
        sum -= a;
    }
 
    cout << sum;
}

Repetition

Problem statement

1. Find the maximum continuous occurrence of a character in the sring

Intuition

1. Two pointers approach (i and j)
2. If val under pointer i is same as j, inc j
   • If max value is less than the current distance between i and j, set max to new distance value
3. If the j character is different, move i to location of j
4. Continue until j reaches the end of the string

Code

int main()
{
    string a;
    unsigned int i = 0, j = 0, max = 0;
    cin >> a;
 
    while (j < a.size())
    {
        if (a[i] == a[j])
        {
            j++;
            if (j - i + 1 > max)
                max = j - i + 1;
        }
        else
            i = j;
    }
 
    cout << max - 1;
}

Increasing Array

Problem Statement

1. We are given n numbers and max value of numbers is n.
2. We need to modify the list of numbers so that the next number is greater than or equal to the previous number
3. Each “move” can increment one number by 1.
4. Result is the minimum number of moves required.

Intuition

1. Iterate the list,
2. If the max value is less than the current max, update max value to new higher value
3. If a number is less than the max value, add the difference to the count variable

Code

int main()
{
    long long unsigned int curr = 0, max = 0, count = 0;
    cin >> curr;
 
    cin >> curr;
    max = curr;
    while (cin >> curr)
    {
        if (max < curr)
            max = curr;
        if (max > curr)
            count += max - curr;
    }
    cout << count;
}

Permutations

Problem Statement

1. We are given a number n
2. We need output numbers 1 to n, so that none of them are next to a number that’s +1 or -1 of the current number.
3. If no solution is possible, output ‘NO SOLUTION’

Intuition

** Common edge cases**

1. Answer to n = 1 is 1. Since that’s suffices the prob statement
2. Numbers 2 and 3 have no solution, since they can be rearranged in any way that satisfies the requirements.

Approach 1

1. Iterate from n to 1
2. Print only even numbers first
3. Then print odd numbers

Approach 2

1. Iterate from n to 1
2. Keep track of last number that was output
3. If the last number isn’t current - 1 output it
4. Else add it to a queue/ vector and data structure of your choice
5. Then output all items from queue
6. This doesn’t work when n = 4 so there is a hardcoded edge case handled in code

Code

Approach 1

int main()
{
    unsigned int n, l;
    cin >> n;
    l = n;
    if (n == 1)
    {
        cout << 1;
        return 0;
    }
    if (n > 1 && n < 4)
    {
        cout << "NO SOLUTION";
        return 0;
    }
 
    while (n > 0)
    {
        if (n % 2)
            cout << n << " ";
        n--;
    }
 
    while (l > 0)
    {
        if (!(l % 2))
            cout << l << " ";
        l--;
    }
}

Appraoch 2

int main()
{
    unsigned int n, l;
    cin >> n;
 
    if (n > 1 && n < 4)
    {
        cout << "NO SOLUTION";
        return 0;
    }
 
    if (n == 4)
    {
        cout << 2 << " " << 4 << " " << 1 << " " << 3 << " ";
        return 0;
    }
 
    l = n;
    cout << n << " ";
    n--;
 
    queue<unsigned int> q;
    for (; n > 0; n--)
    {
        if (l == n + 1)
        {
            q.push(n);
        }
        else
        {
            l = n;
            cout << n << " ";
        }
    }
 
    while (!q.empty())
    {
        cout << q.front() << " ";
        q.pop();
    }
}