Amazon Interview Question for Jr. Software Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
2
of 2 vote

public class NumberOf2 {
public void find2(int num){
for(int i=0;i<=num;i++){
String s = ""+i;
if(s.contains("2")){
System.out.println(""+i);
}
s=null;
}
}
public static void main(String[] args) {
NumberOf2 n = new NumberOf2();
n.find2(21);
}
}

- Pratik Palashikar December 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Guess a corner case need to handle for input values like 22, 222, 2222,....

- Harish kumar December 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi I guess a corner case need to handle for input values like 22, 222, 2222,...

- harishkumar.j1989 December 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Scanner userInput=new Scanner(System.in);
System.out.println("Enter the input number");
int value=userInput.nextInt();
int input2=value;
int repeat=0,k;
for(int i=2;i<=value;i++){
input2=i;
while(input2>0){
k=input2%10;
if(k==2){
repeat++;
}
input2=input2/10;
}

}
System.out.println(repeat);

- vinil November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

crazy complexity,
for input 1.000.000 it makes 5.888.895 iterations.
See below the O(1) solution.

- zr.roman November 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Moreover, your solution will not work with big input integers (which are near to Int32.MaxValue). You will get overflow in Ā«repeatĀ» variable.

- zr.roman November 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think there is a small problem in this source code. the for loop should be

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

}

- Mosley November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int numOfTwo(int n) {
        int ret = 0;
        int digit =0; 

        while (n != 0) {
            int r = n%10, d = n/10;
            if (r>=2) d++;

            ret +=Math.pow(10,digit)*d;

            n = n/10;
            digit++;
        }   
        return ret;
    }

- SK November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

but some input values lead to wrong output, for example: input 20, output 12, while it should be 2.
Input 120, output 32, while it should be 22,
etc.

- zr.roman November 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I improved, see below.

- zr.roman November 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks zr.roman. I saw your solution. I also posted one with fix. I didn't consider overflow handling though.

- SK November 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int numOfTwo(int n) {
int ret = 0;
int digit =0;

while (n != 0) {
int r = n%10, d = n/10;

if (r>=2) d++;

ret +=Math.pow(10,digit)*d;

n = n/10;
digit++;
}
return ret;

}

- SK November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int numOfTwo(int n) {
        int ret = 0;
        int digit =0; 

        while (n != 0) {
            int r = n%10, d = n/10;
            if (r>=2) d++;

            ret +=Math.pow(10,digit)*d;

            n = n/10;
            digit++;
        }   
        return ret;

    }

- Anonymous November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Doesn't work. For 21 gives result 12.

- Anonymous January 27, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int numOfTwo(int n) {
int ret = 0;
int digit =0;

while (n != 0) {
int r = n%10, d = n/10;
if (r>=2) d++;

ret +=Math.pow(10,digit)*d;

n = n/10;
digit++;
}
return ret;

}

- Kang November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int numOfTwo(int n) {
int ret = 0;
int digit =0;

while (n != 0) {
int r = n%10, d = n/10;
if (r>=2) d++;

ret +=Math.pow(10,digit)*d;

n = n/10;
digit++;
}
return ret;

}

- kang November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

c# implementation with the help of algorithm of @SK and @kang.
Time complexity (worst) is O(50*k), where k - number of digits in input value. Actually, for the range of INT numbers the complexity is O(1).

using System;

namespace CountTwos {

    class Program {

         private static long GetCountOfTwos( int num, ref int t ) {

            var lastTwoDigits = num % 100;
            if ( lastTwoDigits == 99 ) {
                return GetNewRes( GetNumOfTwoForBound( num, ref t ), num, i => --i, ref t );
            }

            var numWithoutLast2Digits = (int)Math.Floor( ( num / Math.Pow( 10, 2 ) ) );
            int lowerBound = numWithoutLast2Digits * 100 - 1;
            int upperBound = num >= int.MaxValue - 47 ? int.MaxValue : numWithoutLast2Digits * 100 + 99;

            int bound = upperBound;
            int start = upperBound;
            Predicate<long> condFunc = i => i >= num;
            Func<long, long> incDec = i => --i;
            bool lowerNear = num - lowerBound < upperBound - num;

            if ( lowerNear ) {
                bound = lowerBound;
                start = lowerBound + 1;
                condFunc = i => i < num;
                incDec = i => ++i;
            }

            long res = GetNumOfTwoForBound( bound, ref t );

            for ( long i = start; condFunc.Invoke( i ) ; i = incDec.Invoke( i ) ) {
                res = GetNewRes( res, i, incDec, ref t );
            }
            return res;
        }

        private static long GetNewRes( long res, long curr, Func<long, long> incDec, ref int t ) {
            while ( curr != 0   ) {
                t++;
                var digit = curr % 10;
                if ( digit == 2 ) {
                    res = incDec.Invoke( res );
                }
                curr = curr / 10 ;
            }
            return res;
        }

        // borrowed code from @SK and @kang
        private static long GetNumOfTwoForBound( int n, ref int t ) {
            long ret = 0;
            int digit = 0;

            while (n != 0) {
                t++;
                int r = n % 10;
                int d = n / 10;
                if ( r >= 2 ) d++;

                ret += (long)Math.Pow( 10, digit ) * d;

                n = n / 10;
                digit++;
            }
            return ret;
        }

        static void Main(string[] args) {
            int t = 0;
            Console.WriteLine( $"{ GetCountOfTwos( 82, ref t )}, Complexity: O({t})" );
            Console.ReadLine();
        }
    }
}

- zr.roman November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

unsigned int count2s(int num)
{
	if (num < 3)
		return num == 2 ? 1 : 0;
	string str = to_string(num);
	unsigned int total = 0;
	int len = str.length();
	for (int i = 0; i < len; i++)
	{
		int temp = 0;
		if (i > 0)
			temp += atoi(str.substr(0, i).c_str());

		if (str[i] == '2')
		{
			if (len - i - 1 > 0)
				temp *= (int)pow(10, len - i - 1);
			if(i+1 < len)
				temp += atoi(str.substr(i + 1, len-i-1).c_str()) + 1;
		}
		else
		{
			if (str[i] > '2')
				temp++;
			if (len - i - 1 > 0)
				temp *= (int)pow(10, len - i - 1);
		}
		total += temp;
	}
	return total;
}
int main()
{
	cout << " number of 2s 99 = " << count2s(99) << endl;
	cout << " number of 2s 29 = " << count2s(29) << endl;
	cout << " number of 2s 219 = " << count2s(219) << endl;
	getchar();
}

- siva.sai.2020 November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

for input 23 the output is 7, while it should be 6.

- zr.roman November 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.lang.*;

public class SandboxA {

	private int valueHolder;
	
	public SandboxA(int value)
	{
		valueHolder = myFunc(value);
	}
	
	// solution
	private int myFunc (int targetValue)
	{
		int valCnt = 0;
		String indexStr = "";
		
		for (int index=0; index<targetValue; ++index)
		{
			indexStr = "" + index;
			if (indexStr.contains("2"))
				valCnt++;
		}		
		return valCnt;
	}
	
	public static void main (String [] args)
	{
		int tarVal = 23;
		SandboxA sba = new SandboxA(tarVal);
		
		System.out.println("Count of integers containing the digit '2' in range (0," + tarVal + "): " + sba.valueHolder);
		System.out.println();
	}
}

- jdeshaies1982 November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

for 23 the solution's output is 5, but it should be 6.

- zr.roman November 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the for loop if you replace 'index < targetValue' by 'index<=targetValue' it works fine. It doesn't check the boundary conditions.

- Apoorva December 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Scanner userInput=new Scanner(System.in);
System.out.println("Enter the input number");
int value=userInput.nextInt();
int input2=value;
int repeat=0,k;
for(int i=2;i<=value;i++){
input2=i;
while(input2>0){
k=input2%10;
if(k==2){
repeat++;
}
input2=input2/10;
}

}
System.out.println(repeat);

- Anonymous November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Scanner userInput=new Scanner(System.in);
System.out.println("Enter the input number");
int value=userInput.nextInt();
int input2=value;
int repeat=0,k;
for(int i=2;i<=value;i++){
input2=i;
while(input2>0){
k=input2%10;
if(k==2){
repeat++;
}
input2=input2/10;
}

System.out.println(repeat);

- script7vineel November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

crazy complexity,
for input 1.000.000 it gives 5.888.895 iterations.

- zr.roman November 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int numOfTwo(int n) {
        int ret = 0;
        int digit =0; 
        int temp = n;

        while (temp != 0) {
            int right = 0;
            int r = temp%10, d = temp/10;

            if (r>2) {
                d++;
            } else if (r == 2) {
                if (digit == 0) right = 1;
                else right = n  % (int)Math.pow(10, digit);
            }   
                 

            ret +=Math.pow(10,digit)*d + right;
                
            temp = temp/10;
            digit++;
        }   
        return ret;

    }

- SK November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes, much better, but some small errors stay.
For example, for input 22, the output is 5, but should be 4.
For input 222, the output is 67, but should be 66.
For input 10202, the output is 4043, but should be 4042.
etc.
In general, for all the input numbers that do not contain digit "2", the output is always correct, but for the input numbers that contain digit "2", there could be error output.

- zr.roman November 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(log(10,n)) ~ O(1) for 32 bit int. Note this is for 0 to n.

For m to n just call it twice and subtract

public int countDigitTwo(int n) {

    if (n <= 0) return 0;
    int q = n, x = 1, ans = 0;
    do {
        int digit = q % 10;
        q /= 10;
        ans += q * x;
        if (digit == 2) ans += n % x + 1;
        if (digit >  2) ans += x;
        x *= 10;
    } while (q > 0);
    return ans;

}

- lepeisi November 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// TC: O(logn) the log is based on 10.
public class AMZ_NumOfNums {
    // n>0
    int getNum(Integer n)
    {
        return helper(n-1);
    }

    int helper(Integer n)
    {
        if(n<=1)
            return 0;
        if(2<=n && n<=11)
            return 1;

        String s = n.toString();
        if(s.charAt(0) == '2')
        {
            int low = (int)(n%Math.pow(10, s.length()-1));
            return (low + 1) + helper(n- low - 1);
        }
        else if(s.charAt(0) < '2') {
            int low = (int) (n % Math.pow(10, s.length() - 1));
            return helper(low) + helper(n - low - 1);
        }
        else
        {
            int high = Integer.parseInt("" + s.charAt(0));
            int tens = (int)Math.pow(10, s.length() - 1);
            int low = (int)(n%tens);
            return helper(low+1) + helper(tens-1)*(high-3) + helper(3*tens - 1);
            // this splits n (e.g. 456) into three parts
            // 1. 57 -> this covers 400 to 456
            // 2. helper(99)*1 -> this covers from 300 to 399
            // 3. 299  -> this covers 1 to 299. It uses if(=='2') branch to avoid looping on 99.
        }
    }
}

- jiangok2006 November 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int hm[32] = {0};

int
power (int m)
{
  int sum = 1, m2 = m;
   while (m) {
        sum = sum * 10;
        m--;
   }
   printf("power m %d sum %d", m2, sum);
   getchar();
   return sum;
}

        int
iter (int val, int m)
{
        int sum;

        if (m == 0) {
                if (val >= 2) return 1;
                return 0;
        }

        //for 10's place m = 1, for 100's place m = 2 ...
        if (val > 2) {
                sum = (val - 1)*hm[m] + power(m);
        } else {
                sum = val*hm[m];
        }

        printf(" for m %d val %d \n", m, sum);
        getchar();
        return sum;
}

void
calc_hm (int m)
{

        if (m == 0) {
                hm[m] = 0;
                return;
        } else if (m == 1) {
                hm[m] = 1;
                return;
        }

        hm[m] = 9*hm[m-1] + 10*hm[m-1];
        printf("h[%d] = %d\n", m, hm[m]);
        getchar();
}

        int
main (int argc, char *argv[])
{
        int count, m, sum = 0;
            char *ptr, *save;

        if (argc == 1) return -1;

        ptr = argv[1];
        printf("Ptr %s \n", ptr);
        count = 1;

        while (*ptr != '\0') ptr++;

        ptr--;
        save = ptr;
        printf(" %d %p %p %p\n", (*ptr - '0'), argv[1], ptr, (ptr+1));
        getchar();
        while (ptr >= argv[1]) {
                calc_hm(count);
                ptr--;
                count++;
        }

        ptr = save;
        m = 0;

        while (ptr >= argv[1]) {
                sum += iter((*ptr - '0'), m);
                m++;
                ptr--;
        }

        printf(" sum %d \n", sum);
}

 Inpuput : 475 :
 Output : 174

- Anonymous December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int hm[32] = {0};

int
power (int m)
{
  int sum = 1, m2 = m;
   while (m) {
        sum = sum * 10;
        m--;
   }
   printf("power m %d sum %d", m2, sum);
   getchar();
   return sum;
}

        int
iter (int val, int m)
{
        int sum;

        if (m == 0) {
                if (val >= 2) return 1;
                return 0;
        }

        //for 10's place m = 1, for 100's place m = 2 ...
        if (val > 2) {
                sum = (val - 1)*hm[m] + power(m);
        } else {
                sum = val*hm[m];
        }

        printf(" for m %d val %d \n", m, sum);
        getchar();
        return sum;
}

void
calc_hm (int m)
{

        if (m == 0) {
                hm[m] = 0;
                return;
        } else if (m == 1) {
                hm[m] = 1;
                return;
        }

        hm[m] = 9*hm[m-1] + 10*hm[m-1];
        printf("h[%d] = %d\n", m, hm[m]);
        getchar();
}

        int
main (int argc, char *argv[])
{
        int count, m, sum = 0;
            char *ptr, *save;

        if (argc == 1) return -1;

        ptr = argv[1];
        printf("Ptr %s \n", ptr);
        count = 1;

        while (*ptr != '\0') ptr++;

        ptr--;
        save = ptr;
        printf(" %d %p %p %p\n", (*ptr - '0'), argv[1], ptr, (ptr+1));
        getchar();
        while (ptr >= argv[1]) {
                calc_hm(count);
                ptr--;
                count++;
        }

        ptr = save;
        m = 0;

        while (ptr >= argv[1]) {
                sum += iter((*ptr - '0'), m);
                m++;
                ptr--;
        }

        printf(" sum %d \n", sum);
}

}

- Srinath December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int countDigitTwo(int n) {
if (n < 2)
return 0;
long count = 0;
for (int i = 1; i < n; i = i * 10) {
int a = n / i;
int b = n % i;
count = count + (a + 7) / 10 * i;
if (a % 10 == 2)
count = count + b;
}
return (int) count;
}

- huangsiapply December 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
- raphaelrcampos.rrc December 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

System.out.println("Enter the number:");
	int input = scan.nextInt();
	int count = 0;
	List<Integer> num = new ArrayList<Integer>();
	while(input > 0){
		num.add(input%10);
		input /= 10;
	}
		
	Iterator<Integer> itr = num.iterator();
	while(itr.hasNext()){
		if(itr.next()== 2)
			count++;
	}
	System.out.println(count);

- ashokjune17 December 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class NumberOf2 {


public void find2(int num){

for(int i=0;i<=num;i++){
String s = ""+i;
if(s.contains("2")){
System.out.println(""+i);
}
s=null;
}


}


public static void main(String[] args) {

NumberOf2 n = new NumberOf2();
n.find2(21);


}



}

- Pratik Palashikar December 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class NumberOf2 {
public void find2(int num){
for(int i=0;i<=num;i++){
String s = ""+i;
if(s.contains("2")){
System.out.println(""+i);
}
s=null;
}
}
public static void main(String[] args) {
NumberOf2 n = new NumberOf2();
n.find2(21);
}
}

- Pratik Palashikar December 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

java solution

int num=21;
	
	int rem=0;
	
	int count=0;
	
	for(int i=0;i<=num;i=i+2){
		
		int temp=i;
		
		while(temp>0){
			
			rem=temp%10;
			
			if(rem==2)
				count++;
			
			temp=temp/10;
		}
		
		
		
		
	}

	System.out.println("Total count::"+count);

- rajnish December 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Test 
{
	public static void main(String args[])
	{
		int n = 210;
		int count = 0;
		
		for(Integer i=200; i < n; i++)
		{
			String si = i.toString();
			while(si.contains("2"))
			{
				count++;
				si = si.replaceFirst("2", "0");
			}
		}
		
		System.out.println(count);
	}
}

- Dhavalkumar Patel December 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Scanner;


public class test {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Integer limit = sc.nextInt();

for (int i = 0; i < limit; i++) {
int num = i;
while(num != 0){
int r = num %10;
if(r == 2){
System.out.println(i);
break;
}
num = num /10;
}
}
}
}

- saurabh sharma January 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Scanner;


public class test {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Integer limit = sc.nextInt();

		for (int i = 0; i < limit; i++) {
			int num = i;
			while(num != 0){
				int r = num %10;
				if(r == 2){
					System.out.println(i);
					break;
				}
				num = num /10;
			}
		}
	}
}

- saurabh sharma January 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.dev;

public class P7_NumberOfTwoTillInput {

public static void main(String[] args) {
numberOfTwo("13");
}

private static void numberOfTwo(String input) {
int count = 0;
char[] tmpArray = null;
for (Integer i = 0; i < Integer.parseInt(input); i++) {
if (String.valueOf(i).contains("2")) {
if (String.valueOf(i).length() == 1) {
count++;
} else {
tmpArray = String.valueOf(i).toCharArray();
for (int j = 0; j < tmpArray.length; j++) {
if (tmpArray[j] == '2') {
count++;
}
}
}
}
}
System.out.println(count);
}

}

- alis January 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//this function will return number of occurences of decimalCoefficient INCLUDING Number. So if Number should not be included then call it with Number - 1
        static int countNums(int Number, int decimalCoefficient)
        {
            int coeff = 1; // power of ten here is 0
            int sum = 0;   // init nimber of occurences of decimalCoefficient;
            int numRem = 0;// this variable will hold cut portion of the number (what was lost after it was divided by 10 i itterations of the loop. 
            
            while(Number > 0)
            {
                int rem = Number % 10;
                Number = Number / 10;

                if (Number <= 0)
                {
                    if (rem > decimalCoefficient) //if the most significant digit is greater then decimalCoefficient then add current power of 10 to the sum (count of decimalCoefficient) of  digit;
                        sum += coeff;                   
                }
                else
                {
                    int multiplier = (rem > decimalCoefficient) ? Number + 1 : Number;//number of times decimalCoefficient is repeated in a previous bit 
                    sum = sum + coeff * multiplier;                  
                }

                if (rem == decimalCoefficient)
                    sum = sum + numRem + 1; //if remainder is equal to decimal coefficient then decimalCoefficient will be repeated as many times as numRem
                                            

                numRem = numRem + rem * coeff; // if next significant digt is decimalCoefficient then numRem will serve us in the previous statement;
                coeff *= 10; // get the next power of 10;
            }
            return sum;
        }

- undefined April 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int numberOf2s(int input) {
        int number = input;
        int count = 0;

        int mult = 1;
        while (number > 0) {
            int lastDig = number % 10;

            if (lastDig >= 2) {
                count += 1;
            }

            if (lastDig == 0) {
                lastDig = mult;
            } else {
                lastDig *= mult;
            }

            count += (lastDig / 10);

            mult *= 10;
            number = number / 10;
        }
        return count;
    }

- Bintoo May 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int numberOf2s(int input) {
        int number = input;
        int count = 0;

        int mult = 1;
        while (number > 0) {
            int lastDig = number % 10;

            if (lastDig >= 2) {
                count += 1;
            }

            if (lastDig == 0) {
                lastDig = mult;
            } else {
                lastDig *= mult;
            }

            count += (lastDig / 10);

            mult *= 10;
            number = number / 10;
        }
        return count;
    }

- Bintoo May 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int f(int n) {
int total = 0;
int digit = 0;
while (true) {
int digitValue = (int) Math.pow(10, digit);
int div = n / (digitValue * 10);
int rem = n % (digitValue * 10);

int divContribution = div * digitValue;
int remContribution = 0;
if (rem >= 2 * digitValue) {
remContribution = Math.min(digitValue, rem - 2 * digitValue + 1);
}

int totalContribution = divContribution + remContribution;
total += totalContribution;

if (totalContribution == 0) {
break;
}
digit++;
}
return total;
}

- vitaly.ylativ July 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int f(int n) {
    int total = 0;
    int digit = 0;
    while (true) {
      int digitValue = (int) Math.pow(10, digit);
      int div = n / (digitValue * 10);
      int rem = n % (digitValue * 10);

      int divContribution = div * digitValue;
      int remContribution = 0;
      if (rem >= 2 * digitValue) {
        remContribution = Math.min(digitValue, rem - 2 * digitValue + 1);
      }

      int totalContribution = divContribution + remContribution;
      total += totalContribution;

      if (totalContribution == 0) {
        break;
      }
      digit++;
    }
    return total;
  }

- vitaly.ylativ July 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int f(int n) {
    int total = 0;
    int digit = 0;
    while (true) {
      int digitValue = (int) Math.pow(10, digit);
      int div = n / (digitValue * 10);
      int rem = n % (digitValue * 10);

      int divContribution = div * digitValue;
      int remContribution = 0;
      if (rem >= 2 * digitValue) {
        remContribution = Math.min(digitValue, rem - 2 * digitValue + 1);
      }

      int totalContribution = divContribution + remContribution;
      total += totalContribution;

      if (totalContribution == 0) {
        break;
      }
      digit++;
    }
    return total;
  }

- vitaly.ylativ July 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include <string>
using namespace std;
int twos(int num, char key ='2', int count =0){

for(int i=0; i<num;++i){
string temp = to_string(i);

for(char c:temp) {
if(c==key)++count;
}

}


return count;
}

int main()
{

cout << twos(23);

}

- BR November 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include <string>
using {namespace} std;
int twos(int num, char key ='2', int count =0){

for(int i=0; i<num;++i){
string temp = to_string(i);

for(char c:temp) {
if(c==key)++count;
}

}


return count;
}

int main()
{

cout << twos(23);

}

- BR November 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python solution
Time complexity: O(n)

def number_of_2s(num):
    count = 0
    for x in range (0,num):
        string = str(x)
        if "2" in string:
            count += 1
    return count

- Lawrence Fernandes May 05, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

C++. O(n) time.

int Count2s(int num){
  
  int count = 0;
  while(num > 0){
    int digit = num % 10;
	if(digit == 2) count++;
    num /= 10;
  }
 
  return count;
}

int CountAll2s(int num){

  int count = 0;
  for(int i = 0; i <= num; i += 2){
    count += Count2s(i);
  }
  
  return count;
}

int main(){

  cout << CountAll2s(21) << endl; // 3
  cout << CountAll2s(13) << endl; // 2
  cout << CountAll2s(475) << endl; // 123
  
  return 0;
}

- rob November 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

for(int i = 0; i < num; i += 1)
and your answer is O(n log n) time

- chiky November 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your runtime calculation is not linear. You have a while loop in your Count2s method which depends on the number of digits in n. So essentially you are going through each number once and then calculating its number of digits (Number of digits and number of loops for the biggest number 'n' will be log10 n). Worst case the time complexity should be O (n Log10 n)

- Saurabh November 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public int numOfTwo(int n) {
int ret = 0;
int digit =0;

while (n != 0) {
int r = n%10, d = n/10;
if (r>=2) d++;

ret +=Math.pow(10,digit)*d;

n = n/10;
digit++;
}
return ret;

}

- kang November 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

for input number 300 it gives output 95, but only in range [200...299] we have 100 numbers with 2s.

- zr.roman November 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int countTwos(int input) {
    int count = 0;
    for(int i=0; i<input; ++i) {
        int j=i;
        while(j!=0) {
            if(j%10==2) {
                ++count;
            }
            j=j/10;
        }
    }
    return count;
}

- NewBie November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

crazy complexity,
for input 1.000.000 it gives 5.888.889 iterations.
See the solution below: for input 1.000.000 it gives 6 iterations (it is where worst complexity is O(50*k), k - number of digits in input value ).

- zr.roman November 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

could you clarify a little bit:
what answer should be in case we are given 23 ?
the numbers between 2,12,20,21,22 - total count of numbers is 5, but total count of 2s is 6.
What is the answer?

- zr.roman November 27, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More