Introductory Problems [CSES]

Weird Algorithm

This is a simulation-based problem, we have to multiply the number with 3 and add one if it is odd or divide it by 2 if it is even. Do it till we reach 1.

Missing Numbers

We will be given a number n and n-1 number from 1 to n. We have to find the missing number. Maintained an arr of length n and marked the entry 1 if it appeared. 

Space complexity: O(n)

Create Strings 1:

Given a string, print all different combinations of it in a lexicographically sorted way. Used recursion. GetPermutations takes freq_array and size of expected string and returns the list of permutations possible. For each possible first letter, it appends it with strings returned by GetPermutaions( freq_array with current char removed, size - 1).  Time Complexity: O(2^n)

Apple Division

Given a bunch of apples and their weights, divide them into two groups such that the difference in weights is minimum. The approach here is to find all possible combinations and get the combination with the minimum absolute difference with total total_sum/2. Using the above algorithm to find the total sum for all combinations. This approach led to Timeout. Apparently, a better approach to code with is by using "Looping with BitMask". 

 

  for (int i = 0; i < 1 << n; i++) {
  	// new combination
	for (int j = 0; j <= n; j++) {
    	    if (1 << j & i) {
        	// included in current combination
            }
        }
  }

In this case, we have to find out the sum of each combination so we just have to maintain a sum var in outer for loop and in the inner loop include each element in sum if the IF condition is satisfied.