CareerCup

My answer for n < 10^18. Complexity is O(numbersDigits(n))

def count2(n):
    total2 = [0 for i in range(0, MAX_DIGIT)]

    # total 2s from 0 to 9
    total2[1] = 1

    # continue calculate 2s from 0 to 99, 0 to 999, etc...
    for i in range(2, MAX_DIGIT):
        total2[i] = total2[i - 1] * 10 + 10**(i - 1)

    answer = 0

    # example: 123 = 1 * total2[2] + 2 * total2[1] + 23 + 3 * total2[0] + 10^0
    for i in range(len(n)):
        # calculate number of 2 exists
        value = int(n[i])
        digits = len(n) - i - 1
        answer += value * total2[digits]

        # if this digits is 2, increase answer by all remains value
        if value == 2:
            answer += int("0" + n[i + 1:len(n)]) + 1

        # if this digits is larger than 2, increase answer by 10**digits
        if value > 2:
            answer += 10**digits

    return answer

//ZoomBA
def count_2( n ){
   sum( [2:n+1] ) ->{
      sum ( str($.o).value ) ->{ $.o == '2' ? 1 : 0 }
   }
}

public int numberOfKs(int k,int n){

int count=0;

for(int i=k;i<=n;i++){

if(i==k){
count++;
}

else{
int tmpNum=i;

while(tmpNum!=0){

int rem=tmpNum%10;
tmpNum=tmpNum/10;

if(rem==k){
count++;
}

}

}

}

return count;

}

public class TwoCounter {
	private int n;

	public TwoCounter(int n) {
		this.n = n;

	}

	public void numberOfCount() {
		int length = 0;
		String len = "";
		for (int i = 0; i < n + 1; i++) {
			len += i;

		}
		System.out.println(len);
		char[] newRey = len.toCharArray();

		for (char ch : newRey) {
			if (ch == '2') {
				length += 1;
			}

		}
		System.out.println(length);
	}

}

public class TwoCounter {
	private int n;

	public TwoCounter(int n) {
		this.n = n;

	}

	public void numberOfCount() {
		int length = 0;
		String len = "";
		for (int i = 0; i < n + 1; i++) {
			len += i;

		}
		System.out.println(len);
		char[] newRey = len.toCharArray();

		for (char ch : newRey) {
			if (ch == '2') {
				length += 1;
			}

		}
		System.out.println(length);
	}

}

Lets put F(n) - number of 2s... Lets call F[a1,a2) - number of 2s between a1 and a2-1 and F[a1,a2] - between a1 and a2. So, F(n) == F[0,n] == F[0,n+1).
First, lets see how many 2s are in [0, 10^k]. 
	F(10)= 1;
	F(100) 	= F[0,10)+F[10,20)+F[20,30)+...F[90,100) = 9*F(10) + (10+F(10)) =20
	F(1000) 	= F(100)+F[100,200)+F[200,300)+...F[900,1000) = 9*F(100) + (100+F(100)) = 300
	F(10^(k+1)) = 10^k + 10*F(10^k) = 10^k +10*(10^(k-1) + 10*(...)) = (k+1)*10^k;
So, F(10^k) = k*10^(k-1).
Now, lets present number n as [a0,a1,a2,...,ak] when n = a0+a1*10+...+ak*10^k.
Then, 
	if(ak==0)
		F([a0,a1,a2,...,0]) = 	F([a0,a1,a2,...,a(k-1)]) 
	elseif(ak==1)
		F([a0,a1,a2,...,1]) = 	F([a0,a1,a2,...,a(k-1)]) + 1*F(10^k)
	elseif(ak==2)
		F([a0,a1,a2,...,2]) = 	F([a0,a1,a2,...,a(k-1)]) + 1+[a0,a1,a2,...,a(k-1)] + 2*F(10^k)
	else
		F([a0,a1,a2,...,ak]) = 	F([a0,a1,a2,...,a(k-1)]) + 10^k + ak*F(10^k)

so...
ULONG Count2(ULONG n) {
	ULONG nRet = 0;
	ULONG n10deg = 1;//10^(nK-1)
	ULONG nK = 0;
	ULONG n1 = 0; //a mod 10^nK
	while (n) {
		ULONG a = n % 10;
		switch (a) {
		case 0: break;
		case 1: nRet += nK*n10deg; break;
		case 2: nRet += 1 + n1 + 2 * nK*n10deg; break;
		default: nRet += n10deg + a*nK*n10deg;
		}
		if (nK)
			n10deg *= 10;
		++nK;
		n1 = n1 * 10 + a;
		n /= 10;
	}
	return nRet;
}

Thinking it's O(nm) where n=number of numbers and m is the average # of digits of the numbers

#include <stdio.h>

int twosInRange(int max);
int twosInNum(int n);

int twosInRange(int max) {
    int counter = 0;
    for (int i=0; i<=max; ++i) {
        counter += twosInNum(i);
    }
    return counter;
}

int twosInNum(int n) {
    int counter = 0;
    while (n != 0) {
        if ( (n-2) % 10 == 0 ) {
            counter += 1;
        }
        n /= 10;
    }
    return counter;
}


int main()
{
    int n = 29;
    int ans = twosInRange(n);
    printf("Q: %d\n - Ans: %d\n", n, ans);

    return 0;
}

I think it's O(nm) where n= number of numbers, m= avg # of digits in the numbers.

#include <stdio.h>

int twosInRange(int max);
int twosInNum(int n);

int twosInRange(int max) {
    int counter = 0;
    for (int i=0; i<=max; ++i) {
        counter += twosInNum(i);
    }
    return counter;
}

int twosInNum(int n) {
    int counter = 0;
    while (n != 0) {
        if ( (n-2) % 10 == 0 ) {
            counter += 1;
        }
        n /= 10;
    }
    return counter;
}


int main()
{
    int n = 29;
    int ans = twosInRange(n);
    printf("Q: %d\n - Ans: %d\n", n, ans);

    return 0;
}

I think its O(nm) where n= # of numbers, m=avg # of digits in each number

#include <stdio.h>

int twosInRange(int max);
int twosInNum(int n);

int twosInRange(int max) {
    int counter = 0;
    for (int i=0; i<=max; ++i) {
        counter += twosInNum(i);
    }
    return counter;
}

int twosInNum(int n) {
    int counter = 0;
    while (n != 0) {
        if ( (n-2) % 10 == 0 ) {
            counter += 1;
        }
        n /= 10;
    }
    return counter;
}


int main()
{
    int n = 29;
    int ans = twosInRange(n);
    printf("Q: %d\n - Ans: %d\n", n, ans);

    return 0;
}

I'm going to assume that the numbers are in base 10 and that the digits are counted independently - i.e. 22 counts as two 2's.

This solution iteratively takes the most significant digits, converts them into their own integer, and adds that to the total. Each of these numbers represent the number of 2's in the following decimal place. For example, in the number 540, the number 54 is the number of 2's in the ones place. We'll also add 1 depending on whether the digit in the following decimal place is greater than or equal to 2.

def count2s(n):
    n = '0' + str(n)
    c = len(n)
    total = 0
    for i in range(1, c):
        total += int(n[0:i]) + (int(n[i])>=2)

    return total

ulong numberOfKs(ulong n, byte K)
{
    if (K > 9) throw new ArgumentOutOfRangeException("K");
    ulong sum = 0, pow = 1, i = n;
    while (i > 0)
    {
        ulong fullTens = i / 10;
        ulong reminder = i % 10;
        if (reminder > K)
            fullTens += 1;
        sum += fullTens * pow;
        if (reminder == K)
            sum += n % pow;
        i = i / 10;
        pow = pow * 10;
    }
    return sum;
}

public static int counting2s(int num)                        //Time Complexity: 
        {

            int cnt = 0;
            for (int i = 0; i <= num; i++)
            {

                int currnum = i;
                while (currnum!= 0)
                {
                    int digit = currnum % 10;
                    if (digit == 2)
                        cnt++;

                    currnum = currnum / 10;
                }

            }

            return cnt;
        }

What do you think?

public static int counting2s(int num)                        
        {

            int cnt = 0;
            for (int i = 0; i <= num; i++)
            {

                int currnum = i;
                while (currnum!= 0)
                {
                    int digit = currnum % 10;
                    if (digit == 2)
                        cnt++;

                    currnum = currnum / 10;
                }

            }

            return cnt;
        }

public class Count2InNumber {

public static String removeString(String s, String[] arr){

for(int j=0;j<arr.length;j++){
for(int i=0;i<=arr.length-1;i++){
if(s.indexOf(arr[i])!=-1){
s = s.replaceAll(arr[i], "");

System.out.println("a[i]: "+arr[i]);
System.out.println("String : "+s);
}
}
}
return s;
}

public static void main(String[] args){
Scanner scan = new Scanner(System.in);
System.out.println("Enter the nth number");
int n = scan.nextInt();
int count = 0;


for(int i = 2;i<=n;i++){


String s = new String(new Integer(i).toString());
char[] arr = new char[s.length()];
arr= s.toCharArray();

for(int j = 0; j<arr.length;j++){
if(arr[j]=='2'){
count++;
}

}

}

System.out.println("Nunber of 2's from 0..."+n+"number "+ count);


}//end of main

}//end of class

public class Numof2s {
	
	static int count =0;

	public static void main(String[] args) {
		
		int n =32;
		int i;
		int num;
		
		for(i=1;i<=n;i++)
		{
			num =i;
			while(num!=0)
			{
				if(num%10==2)
					count++;
				num=num/10;
			}
		}
		
		System.out.println(count);
	

	}

}

public class NumOfTwos {

	public static void main(String[] args) {
	
		int n=40;
		int no=1;
		int rem=0;
		int count=0;
	for(int i=1;i<=n;i++)
	{	
		no=i;
	
		while(no>0)
		{
			rem=no%10;
			if(rem==2)
			{
				count++;
				System.out.println(no);
			}
			no=no/10;
				
		}
		
	}	
		System.out.println(count);
		
	}

}

from collections import Counter


def count_2s(n):
    twos = 0
    for i in xrange(n):
        counter = Counter(str(i))
        twos += counter.get('2', 0)
    return twos

from collections import Counter

def count_2s(n):

twos = 0

for i in xrange(n):

counter = Counter(str(i))

twos += counter.get('2', 0)

return twos

from collections import Counter


def count_2s(n):
    twos = 0
    for i in xrange(n):
        counter = Counter(str(i))
        twos += counter.get('2', 0)
    return twos

from collections import Counter

def count_2s(n):
twos = 0
for i in xrange(n):
counter = Counter(str(i))
twos += counter.get('2', 0)
return twos

from collections import Counter

def count_2s(n):
    twos = 0
    for i in xrange(n):
        counter = Counter(str(i))
        twos += counter.get('2', 0)
    return twos

from collections import Counter
def count_2s(n):
    twos = 0
    for i in xrange(n):
        counter = Counter(str(i))
        twos += counter.get('2', 0)
    return twos

static void Main(string[] args)
{
int n = 10;//use any value
int c=0;
while (n != 0)
{
int n1 = n;
do
{
int n2 = n1 % 10;
if (n2 == 2)
{
c++;
}
n1 = n1 / 10;

} while (n1 != 0);
n--;
}

Console.WriteLine(c);
Console.ReadKey();


}

static void Main(string[] args)
        {
            int n = 10;
            int c=0;
            while (n != 0)
            {
                int n1 = n;
                do
                {
                    int n2 = n1 % 10;
                    if (n2 == 2)
                    {
                        c++;
                    }
                    n1 = n1 / 10;

                } while (n1 != 0);
                n--;
            }
         
            Console.WriteLine(c);
            Console.ReadKey();

dddd

dddd

Usage: getCountsfast(12345,'2');

unsigned int getCountsfast(unsigned int uiNum, char ch)
{
    if((uiNum>=0) && (uiNum<=9)){
         // single digit number
         if(uiNum+'0' >= ch){
            // If the number is >= required char, return 1.
            return 1;
         }else {
            // Else, return 0.
            return 0;
         }
    }else {
        // 2 or more more digits in number
        // 499 = 4(20)+100+20 = 200
        //counts(ba,x) = b*counts(9,x)+ ((b>x)? 10:0) + ((b==x)? rem:0)+ counts(a,x)
        //counts(cba,x) = c*counts(99,x) + ((c>x)?>100:0) + ((c==x)? rem:0) + counts(ba,x);

        unsigned int uiNumTmp = uiNum/10;
        unsigned int uiPow = 1;
        while(uiNumTmp > 0){
            uiPow = uiPow*10;
            uiNumTmp = uiNumTmp/10;
        }
        unsigned int uiMsd = uiNum / uiPow;
        unsigned int uiRem = uiNum - (uiMsd*uiPow);
        unsigned int uiFullCounts = uiMsd*getCountsfast(uiPow-1,ch);
        unsigned int uiMidCounts = ((uiMsd+'0'>ch)?uiPow:0) + ((uiMsd+'0'==ch)?(uiRem+1):0);
        unsigned int uiRemCounts = getCountsfast(uiRem,ch);
        return uiFullCounts + uiMidCounts+ uiRemCounts;
    }
}

public static void numberOfTwos(int n) throws Exception
{
int twosCount = 0;
int factor = 0;

if( n < 0 )
{
throw new Exception();
}

while( n != 0 )
{
int lsd = n % 10;

twosCount += lsd * factor;

if( lsd >= 2 )
{
twosCount++;
}

n /= 10;
factor = factor * 10 + 1;
}

System.out.println("twos: " + new Integer(twosCount));
}

public static void numberOfTwos(int n) throws Exception
	{
		int twosCount = 0;
		int factor    = 0;
		
		if( n < 0 )
		{
			throw new Exception();
		}
		
		while( n != 0 )
		{
			int lsd = n % 10;
			
			twosCount += lsd * factor;
			
			if( lsd >= 2 )
			{
				twosCount++;
			}
			
			n /= 10;
			factor = factor * 10 + 1;
		}
		
		System.out.println("twos: " + new Integer(twosCount));
	}

public static void numberOfTwos(int n) throws Exception
	{
		int twosCount = 0;
		int factor    = 0;
		
		if( n < 0 )
		{
			throw new Exception();
		}
		
		while( n != 0 )
		{
			int lsd = n % 10;
			
			twosCount += lsd * factor;
			
			if( lsd >= 2 )
			{
				twosCount++;
			}
			
			n /= 10;
			factor = factor * 10 + 1;
		}
		
		System.out.println("twos: " + new Integer(twosCount));
	}

#include<stdio.h>
#include<conio.h>
int main()
{
int a[20],c,n,r,i;
c=0;
printf("\n enter the no. of integers you wamt to insert:");
scanf("%d",&n);
printf("\n enter the no. of integers:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n the no. of 2s are:");
i=0;
while(i<n)
{
while(a[i]!=0)
{
r=a[i]%10;
if(r==2)
c++;
a[i]=a[i]/10;
}
i++;
}
printf("%d",c);

getch();
}

#include<stdio.h>
#include<conio.h>
int main()
{
int a[20],c,n,r,i;
c=0;
printf("\n enter the no. of integers you wamt to insert:");
scanf("%d",&n);
printf("\n enter the no. of integers:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n the no. of 2s are:");
i=0;
while(i<n)
{
while(a[i]!=0)
{
r=a[i]%10;
if(r==2)
c++;
a[i]=a[i]/10;
}
i++;
}
printf("%d",c);
getch();
}

#include<stdio.h>
#include<conio.h>
int main()
{
	int a[20],c,n,r,i;
	c=0;
	printf("\n enter the no. of integers you wamt to insert:");
	scanf("%d",&n);
	printf("\n enter the no. of integers:");
	for(i=0;i<n;i++)
	scanf("%d",&a[i]);
	printf("\n the no. of 2s are:");
	i=0;
	while(i<n)
	{
		while(a[i]!=0)
		{
		r=a[i]%10;
		if(r==2)
		c++;
		a[i]=a[i]/10;
	}
	i++;
	}
	printf("%d",c);
	getch();
}

it is actually o(1) solution

function(int N)
{
	inf half = floor((float)N/2);
	return half * (half + 1) /2;

Here is my code in C++.
Starting from the most significant digit,
count the number of 2s appeared in the digit.

using ulong = unsigned long long;

ulong count2Range(ulong n)
{
  string N = to_string(n);
  ulong cnt = 0;

  for(int pos = 0; pos < N.size(); pos++){
    int digit = N.size() - 1 - pos;
    // count contribution at the digit
    // while counting upto [0...pos] * 10^i
    if(pos != 0){
      ulong t = atoi(N.substr(0, pos).c_str());
      cnt += t * pow(10, digit);
    }

    // after [0...pos] * 10^i
    if(N[pos] - '0' >= 3){
      cnt += pow(10, digit);
    }
    else if(N[pos] - '0' >= 2){
      cnt += 1;
      if(pos != N.size() - 1)
        cnt += atoi(N.substr(pos + 1).c_str());
    }
  }

  return cnt;
}

Using regex library of python.

import re

pattern=re.compile("2")
MAX_DIGIT=200;
occ=0;
for i in range(0,MAX_DIGIT+1):
	occ+=(len(pattern.findall(str(i))))
print(occ)