Amazon Interview Question Jr. Software Engineers
Country: United States
Interview Type: Phone Interview
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);
crazy complexity,
for input 1.000.000 it makes 5.888.895 iterations.
See below the O(1) solution.
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;
}
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.
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;
}
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();
}
}
}
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();
}
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();
}
}
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);
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);
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;
}
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.
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;
}
// 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.
}
}
}
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
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);
}
}
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);
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;
}
}
}
}
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;
}
}
}
}
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);
}
}
//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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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)
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;
}
public class NumberOf2 {
- Pratik Palashikar December 07, 2015public 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);
}
}