Выпуск#8: ITренировка — актуальные вопросы и задачи от ведущих компаний

Можно посчитать, сколько раз каждый бит (с номером 0,1,2...) будет встречаться в значении 1 в числах от 1 до n.

Если выписать в двоичном виде числа 0,1,2,3,4,5..., то можно увидеть, что:
0-й бит встречается в каждом втором числе, паттерн: 0,1,0,1,0,1,0,1,…
1-й бит встречается дважды в каждой четвёрке чисел, паттерн: 0,0,1,1,0,0,1,1,…
2-й бит встречается четырежды в каждой восьмёрке чисел, паттерн: 0,0,0,0,1,1,1,1,…
…
n-й бит встречается (2^n) раз в каждой полной группе из (2^(n+1)) чисел.

Дополнительно нужно обработать "остатки" от деления числа n на степени 2-ки.
Допустим, число 14 дало остаток 6 при делении на 8. При этом, в числах от 9 до 14 второй бит встретится в значении 1 трижды (числа 12,13,14), и эти 3 единичных бита тоже добавляем к результату.

using System;

class Solution
{
    static void Solve(int n)
    {
        int result = 0;

        for (int k = 1; k <= n; k = k << 1)
        {
            result += k * (n / (k << 1));
            result += Math.Max(((n % (k << 1)) + 1) - k, 0);
        }

        Console.WriteLine($"n = {n}, result = {result}");
    }

    static void Main(string[] args)
    {
        foreach (int n in (new int[] { 3, 6, 7, 8 }))
            Solve(n);
    }
}

public static int[] largestSubarray(int[] array){
        final int n = array.length+1;
        int[] secondArray = new int[n];
        int c = 0;
        // Первый проход - заполняем массив
        for(int i=0; i<array.length; i++){
            if(array[i]==1){
                c++;
            }else{
                c--;
            }
            secondArray[c%n]=i;
        }
        // Второй проход - ищем максимальную длинну подмассива
        c = 0;
        int index = -1;
        int maxValue = secondArray[0]+1;
        for(int i=0; i<array.length; i++){
            if(array[i]==1){
                c++;
            }else{
                c--;
            }
            if(secondArray[c%n]-i>maxValue){
                maxValue = secondArray[c%n]-i;
                index = i;
            }
        }
        // Если найден подмассив
        if(maxValue>1){
            int result[] = new int[2];
            result[0] = index+1;
            result[1] = index+maxValue;
            return result;
        }
        return null;
    }

public static int totalBits(int value){
        int count =0;
        int mask = 1;// 0001, 0010, 0100, 1000 ...
        int mask2 =0;// 0000, 0001, 0011, 0111 ...
        while(value>mask){   
            count+=(value&mask2);
            count+=(value -(value&(mask+mask2)) )/2;
            mask2+=mask;
            mask = mask + mask;
        }
        return count;
    }

public static int[] findRepeatingMissing(int[] array){
        int a =0;
        long b =0;
        for(int i=0; i<array.length; i++){
            a+=array[i]-i;
            b+=array[i]*array[i]-i*i;
        }
        int result[] = new int[2];
        result[0] = (int)(a+b/a)/2;
        result[1] = a - result[0];
        return result;
    }