1. Find the number of set bits in a number. Basically the number of bits that are set to one. Assume the input is 64 bits large, so use long int or long long int as the input type. Keep in mind that the % and the / operators are expensive in nature (they involve more hardware level computation) so use bit operators like << which bit shifts to the left and & which does a bitwise AND of the two numbers (basically the same as boolean AND, but done in a bit-by-bit fashion).

   Input:

   100
   8
   23
   

   Output:

   3
   1
   4
   

2. An array consists of \(2*k + 1\) elements where each element appears twice except for one particular element. Do this question without any variable storage except for the output. You have to compute this as and when the input comes, so you can't store the input in an array either. No addition, subtraction, multiplication, division or mod.

   Input: First number denotes the length

   3 100 100 1
   15 8 8 4 5 6 5 4 12 12 34 25 34 34 25 34
   1 23
   

   Output:

   1
   6
   23
   

3. You are given two numbers \(a\) and \(b\) such that \(a > b\). Find the quotient of the division of \(a\) with \(b\) in \(\mathcal{O}\left(log(a)\right)\) iterations. No division, multiplication, or mod operator. Be smart. I'm not giving you the input testcases because I'm sure y'all can do this by yourself.
4. Calculate the square of a number without using multiplication, division, addition, subtraction or mod. Do it in \(\mathcal{O}\left(log(a)\right)\) iterations. Be smart about your choice of operators.
5. Calculate the GCD of two numbers in \(\mathcal{O}(log(min(a, b)))\) time. No extra variables. Try using recursion if you know how functions work.

1. Range queries. Most of you have solved it already, but here it is: Given an array of length \(n\), initially all zeroes and \(q\) queries. Each query is of the form \(l, r, k\), where you have to add \(k\) to the array from \(l\) inclusive to \(r\) exclusive. Output the final array. Do this in \(\mathcal{O}(n + q)\) iterations without using any extra array. Construct testcases on your own using this python script

   import random
   def testgen():
       n = random.randint(1,100)
       q = random.randint(1, 20)
       lst = [0] * n
       print(n, q)
       for i in range(q):
           l = random.randint(0, n)
           r = random.randint(l, n)
           k = random.randint(1, 5)
           print(l, r, k)
           for i in range(l, r):
               lst[i] += k
       print("==========================")
       print(lst)
   testgen()
   

2. Find the \(K'th\) maximum element in an array in one iteration of the array. Do it in a single sweep of the array. You are allowed to keep an extra array of \(K\) elements. ASsume all elements are positive. Testcase generator is below:

   import random
   def testgen():
       n = random.randint(1, 100)
       k = random.randint(1, n)
       print(n, k)
       lst = [random.randint(1, 250) for i in range(n)]
       print(lst)
       lst.sort(reverse = True)
       print(lst[k])
   
   testgen()
   

3. Like lab 9 Q2, you're given a binary string \(s\) that indicates whether wifi is available in a room or not. Similarly, a number \(k\) indicates how many adjacent rows of rooms can connect to the wifi. Find out whether or not every room can connect to wifi in at most two iterations of the string. Can you do it in one? No extra arrays or variables allowed.

   import random
   def testgen():
       print(format(random.randint(1,2**64), '064b'), random.randint(1, 64))
   testgen()
   

4. Why do you think arr[2] and 2[arr] both work in evaluating the array? If you don't know already, arrays are mostly the same as pointers. Can you make a general observation on (expr1)[expr2], where one of them is supposed to evaluate to an array, and the other one evaluates to the index, or some weird mix in between? Try evaluating (arr/2)[arr/2]. Instead of using arr[2] = 1, try doing *(arr + 2) = 1.

5. Given an array which consists of only 0s, 1s and 2s, sort the array in place in a single sweep. Only three extra variables allowed

   import random
   def testgen():
       print(1000, [random.randint(0,2) for _ in range(0, 1000)])
   
   testgen()
   

6. Rotate an array leftwards in place by \(k\) elements in exactly \(\mathcal{O}(n)\) iterations. Do it properly this time loafers!

   import random
   def testgen():
       n = random.randint(1, 20)
       k = random.randint(0, n)
       lst = [i + 1 for i in range(0, n)]
       print(n, k)
       print(lst)
       print("==================================")
       print(lst[k:] + lst[:k])
   
   testgen()
   

7. Find the union and intersection of two sorted arrays. Solve it in \(\mathcal{O}(n + m)\) iterations. You can keep an extra array for this. The original arrays may not have all unique elements.

   import random
   def testgen():
       n = random.randint(1, 200)
       m = random.randint(1, 200)
       print(n, m)
       lst1 = [random.randint(1, 100) for _ in range(n)]
       lst2 = [random.randint(1, 100) for _ in range(m)]
       lst1.sort()
       lst2.sort()
       print(lst1)
       print(lst2)
       print("==================================")
       print(set(lst1 + lst2))
       print(set.intersection(set(lst1), set(lst2)))
   
   testgen()
   

8. Find the least prime factor of all numbers from 2 to \(n\) in exactly \(n\) iterations. Use just one array in total.

   import random
   def is_prime(p):
       count  = 0
       for i in range(2,p):
           if p%i == 0:
               count += 1
       return count == 0
   #print(is_prime(3))
   def least_prime(k):
       for i in range(2, k):
           if is_prime(i) and k%i == 0:
               return i
       return k
   
   n = random.randint(1, 100)
   print(n)
   print([least_prime(i) for i in range(2, n)]) 
   

9. Merge two sorted arrays with at most one iteration of both the arrays combined. Merge them in a new array.

import random
def func():
    n = random.randint(1, 100)
    m = random.randint(1, 100)
    print(n, m)
    lst1 = [random.randint(1, 100) for _ in range(1, n)]
    lst2 = [random.randint(1, 100) for _ in range(1, m)]
    lst1.sort()
    lst2.sort()
    for i in lst1:
        print(i)
    for i in lst2:
        print(i)
    lst1 += lst2
    lst1.sort()
    print("==============================")
    print(lst1)

func()

NO GLOBAL/STATIC VARIABLES! NO FOR/WHILE LOOPS!

Try using as few parameters as possible.

1. Recursively rotate an array leftwards by \(k\) places. No bounds on time limit.
2. You have a size \(n\). There is an array \(arr\) of size \(n\). Each entry in \(arr\) denotes the size of the array in \(multi-arr\). Each element in \(multi-arr\) is an integer array. You have to create a larger array of size \(\sum{arr[i]}\) such that each element is in the larger array.

3. Recursively eliminate all adjacent duplicates from an array. The first number denotes the length of the initial array and the second denotes the length of the resultant array.

   Input:

   5 3
   1 1 2 3 3
   

   Output:

   1 2 3
   

1. Determine the list of prime factors and their maximum power for an integer \(n\) recursively. You can use the array you obtained from Q8 of Arrays section for this question.
2. Calculate the Euler's totient function \(\phi(m)\) for a given integer \(m\) recursively. The previous question might be helpful.

Pointers are nothing but data that points to other things in memory. They hold memory locations. Really, that's all there is to it.

#include <stdio.h>

int main(void)
{
    int i = 10;

    printf("The value of i is %d\n", i);
    printf("And its address is %p\n", (void *)&i);

    // %p expects the argument to be a pointer to void
    // so we cast it to make the compiler happy.
}

The address of anything can be obtained with & in front of it. To get the value from the address, use * in front of it.

Note on pointer declaration: int *p, q; over here only p is a pointer, q is a regular int.

For an array, read the question above on array and pointer equivalence.