Microsoft Interview Question Software Developers
Country: United States
Thanks for you reply CasaPanacea. I understand the question only after understanding your code :)
There is a simpler solution for the case of 1 to 100,000 which can be generalized. Since there are 5 odds digits (1,3,5,7,9) only, there are 25 (5 * 5) two digit numbers with odd digits. In case of 4 digit numbers there will be 625 (5 to power of 4). So the answer to this specific question can be computed simply by adding 625 + 25 which is 650. I haven't written the solution for any number, it takes a little more work, but it's a much more efficient solution.
#include<conio.h>/*mukesh100592@gmail.com*/
#include<stdio.h>
void main()
{long int nu,dig,i,odcnt,totalnums=0;
clrscr();
for (i=0;i<=100000;i++)
{ odcnt=0;
nu=i;
while(nu>0)
{ dig=nu%10;
if((dig%2)!=0)
odcnt++;
nu=nu/10;
}
if((odcnt%2)==0)
totalnums+=1;
}
printf("total numbers between 1 & 100000 which have even no. of odd digits=%ld",totalnums);
getch();
}
#include<conio.h>
#include<stdio.h>
void main()
{long int nu,dig,i,odcnt,totalnums=0;
clrscr();
for (i=0;i<=100000;i++)
{ odcnt=0;
nu=i;
while(nu>0)
{ dig=nu%10;
if((dig%2)!=0)
odcnt++;
nu=nu/10;
}
if((odcnt%2)==0)
totalnums+=1;
}
printf("total numbers between 1 & 100000 which have even no. of odd digits=%ld",totalnums);
getch();
}
#include<conio.h>
#include<stdio.h>
void main()
{long int nu,dig,i,odcnt,totalnums=0;
clrscr();
for (i=0;i<=100000;i++)
{ odcnt=0;
nu=i;
while(nu>0)
{ dig=nu%10;
if((dig%2)!=0)
odcnt++;
nu=nu/10;
}
if((odcnt%2)==0)
totalnums+=1;
}
printf("total numbers between 1 & 100000 which have even no. of odd digits=%ld",totalnums);
getch();
}
if I modify your code and run it for 1 to 100 I can see it gives totalnums=50
However this in not correct
What I understand that number of digit in a number should be odd
is..
2 4 6 8 are even number which having only 1 digit and 1 is odd number
10 12 14 18 ……are even number but number of digit in these number are 2. 2 is not odd number hence we gonna discard all these number
102 104 106 …. Are even number and number of digit in these number is 3 that is odd number hence we will count these number
1000 1002 1004….are even number and number of digit in these number is 4 that is even number hence we will not count these number…
Please let me know if you think differntly
James, I think you missunderstood the question you wrote yourself. You need to count the numbers with an even number of odd digits, while in your last post you consider just an odd number of digits.
It is pretty easy to prove that this number will be half of all the numbers you consider in a consecutive sequence: Pair every second number n with n+1. If n had an even number of odd digits, n+1 will not, and vice versa. So every pair has one number satisfying the criterion. Since there are half as many pairs as numbers considered, the solution will be half of all of the numbers ( potentially +1 if there is an odd number of numbers considered.)
Following Algorithm should work:
1. Find out highest power of 10 which is lesser than the number provided (call this highest power)
2. Find out delta (input number - highest power of 10 less than the input number) (call this delta)
3. For every odd power of 10 less than highest power find out the numbers between the odd power and the even power less than that power (Call this number to evaluate)
4. even number of odd digits are: number to evaluate/2 for every power evaluated in step above
5. add delta/2 to even number of odd digits if highest power is less odd.
O(log10n)
It may be possible to leverage combinatorics to simplify the algo. Although, it's very easy to be in error. Would be helpful to create several test cases to verify...
1,3,5,7,9 odds
2,4,6,8 evens
Assume the max length of an unsigned int is 6. Sum the following:
4^6 # 0 odds, 4 evens in each position
(5 2)*2!*(6 2)*(4^4) # 2 odds in 2 positions, evens in 4 positions
(5 4)*4!*(6 4)*(4^2) # 4 odds in 4 positions, evens in 2 positions
(5^6) # all odds, 5 odds in each position
bool isAllOddDigits(int number)
{
while (number > 0)
{
int digit = number % 10;
if ((digit % 2) == 0)
return false;
number = number / 10;
}
return true;
}
int evenNumOfOddDigits(const int & maxNumber)
{
int count = 0;
int powerOf10 = 1;
while (true)
{
// Start with 2 digit odd number (e.g. 11) then 4 digit (1001) and so on
int from = (int)pow(10, powerOf10) + 1;
if (from > maxNumber)
break;
// Go up to next power of 10
int to = (int)pow(10, powerOf10 + 1);
// From 11 to 99 then 1001 to 9999 and so on
for (int i = from; i < to; i += 2) // Skip even numbers since then have an even digit
if (isAllOddDigits(i))
count++;
// Skip over numbers that don't have an even number of digits
powerOf10 += 2;
}
return count;
}
bool isAllOddDigits(int number)
{
while (number > 0)
{
int digit = number % 10;
if ((digit % 2) == 0)
return false;
number = number / 10;
}
return true;
}
int evenNumOfOddDigits(const int & maxNumber)
{
int count = 0;
int powerOf10 = 1;
while (true)
{
// Start with 2 digit odd number (e.g. 11) then 4 digit (1001) and so on
int from = (int)pow(10, powerOf10) + 1;
if (from > maxNumber)
break;
// Go up to next power of 10
int to = (int)pow(10, powerOf10 + 1);
// From 11 to 99 then 1001 to 9999 and so on
for (int i = from; i < to; i += 2) // Skip even numbers since then have an even digit
if (isAllOddDigits(i))
count++;
powerOf10 += 2; // Skip over numbers that don't have an even number of digits
}
return count;
}
This is rather brute-force. I don't know if there's a formula to this because I haven't seen a pattern like what's described by oggo above. That doesn't seem right because if applied from 1-10, there's not even a single one with even # of odd digit. The first one is 11.
Here's the simple python brute-force:
lim=100000
count=0
for i in range(1,lim+1):
l = map(int, str(i))
odd_digits = 0
msg = ''
for x in 1,3,5,7,9:
odd_digits += l.count(x)
if odd_digits > 0 and (odd_digits % 2) == 0:
count += 1
msg = '\t===> FOUND!\t%s' % count
print "%s: %s%s" % (i,odd_digits,msg)
print "Number with even odd digits from 1 to %s: %s" % (lim,count)
lim=100000
count=0
for i in range(1,lim+1):
l = map(int, str(i))
odd_digits = 0
msg = ''
for x in 1,3,5,7,9:
odd_digits += l.count(x)
if odd_digits > 0 and (odd_digits % 2) == 0:
count += 1
msg = '\t===> FOUND!\t%s' % count
print "%s: %s%s" % (i,odd_digits,msg)
print "Number with even odd digits from 1 to %s: %s" % (lim,count)
One thing people miss is 0 is an even number, so 0 odd digits also counts (ex. 88, 20, 860)
Here are the answers for various number ranges:
(0 to 9): 5
(0 to 99): 50
(0 to 999): 500
(0 to 9999): 5000
(0 to 99999): 50000
Explanation utilizes combinatorics:
Odd digits: 1, 3, 5, 7, 9 = count of 5
Even digits: 0, 2, 4, 6, 8 = count of 5
For 1 digit, can only have 1 even digit, so answer is 5
For 2 digits, can have 2 odd digits or 2 even digits, so answer is 5*5 + 5*5 = 50
For 3 digits, can have any combination of 2 odd and 1 even digit or 3 even digits = 5^3 + 5^3 + 5^3 + 5^3 = 500
For 4 digits, can have any combination of 2 odd and 2 even digits or 4 even digits or 4 odd digits = 6*5^4 + 5^4 + 5^4 = 5000
For 5 digits, same logic yields 50000
The answer for 100000 is 50000, solves in O(1) time via equation above.
This pattern can be expanded to any provided range to solve the problem in O(k) time where k is the number of digits (length of equation being computed does slowly increase as the number of digits increases).
Ex. write code to calculate count in range [x, y] that contain an even number of odd digits
Brute force code below to check answers I wrote out above:
// Return number of numbers in [0, n] with an even number of odd digits
public static int numEvenOddDigits(int n) {
int total = 0;
for (int i = 0; i <= n; i++) {
int j = i;
int numOddDigits = 0;
while (j > 0) {
if ((j % 10) % 2 == 1) {
numOddDigits++;
}
j /= 10;
}
if ((numOddDigits % 2) == 0) {
System.out.println(i);
total++;
}
}
return total;
}
I think the meaning of this problem is how many numbers in range [1, 100000] contains an EVEN NUMBER of ODD DIGIT, which means the numbers should have odd digit(don't count 0 odd digit numbers), and the count of odd digit should be even, like 11, 13, 15, 110, 1100... and not 1, 3, 12, 111...
Actually it's a intricate problem.
I use brute force method checked numbers in range [1, 20000] and [100000, 106000] and the following method is correct.
int countSmall(int st, int en) {
if (st > en) return 0;
int res = 0, oddcount = 0, tmp;
for (int i = st; i <= en; ++i) {
tmp = i;
oddcount = 0;
while (tmp) { if (tmp & 1) ++oddcount; tmp /= 10; }
if (oddcount % 2 == 0 && oddcount) res++;
}
return res;
}
int countEvenOdd(int end) {
int fullcount = end / 100 ;
int res = fullcount / 2 * 75;
res += countSmall(fullcount * 100, end);
int tmp = fullcount - 1, oddcount = 0;
while (tmp) { if (tmp & 1) ++oddcount; tmp /= 10; }
if (fullcount) res += 25 * countEvenOdd(fullcount - 1);
if (fullcount & 1) res += (oddcount & 1) ? 50 : 25;
return res;
}
correct me if I'm not right, thanks.
#include<iostream>
using namespace std;
int main(void) {
int a[100001];
a[0] = 0;
int count = 0;
for (int i = 1; i < 10; i++) {
if (i % 2 == 1) {
a[i] = 1;
}
else {
a[i] = 0;
}
}
for(int i = 10; i < 100001; i++) {
int quotient = i / 10;
int reminder = i % 10;
a[i] = a[quotient] + a[reminder];
}
for (int i = 1; i < 100001; i++) {
if (a[i] % 2 == 0) {
count++;
}
}
cout << count << endl;
getchar();
return 1;
}
Simple solution,
The valid input ranges are ,since odd digits only, 0 - 9; 100 - 999, 10 - 99,999. there are the ranges that contribute to the total. the ranges in the middle are even digits. so ignore
to get how many in each range, just subtract lower range from upper range and divide it by 2.
the code is
int getCount(int n){
if(n < 0 || n >100,000) return -1
if(n < 10)
return (n/2);
else if (10 <= n < 1,000)
return ((998 - 100)/2 + 8/2 )
else if (1000 <= n < 100,000)
return ((99,999 - 1,000)/2 + (998 - 100)/2 + 8/2)
}
Even number of odd digits,
Eg : 9942, 11, 101 etc.
#include <iostream>
bool evenNumOddDigits(int num)
{
int count = 0;
while(num)
{
int rem = num % 10;
num = num/10;
if(rem % 2)
{
count++;
}
}
if(count % 2 == 0 and count > 0) return true;
return false;
}
int main()
{
int count = 0;
for (int i = 0; i < 10000; i++)
{
if(evenNumOddDigits(i))
{
// std::cout << i << std::endl;
count++;
}
}
std::cout << count;
return 0;
}
public void Even_Number_With_Odd_Digits()
{
// Number of digit in a num should be ODD
// Number should be even
int number = 100000;
int loop_cnt = 0;
int rqd_num = 0;
for (; loop_cnt < number ; loop_cnt++)
{
if (IsOddDigit(loop_cnt))
{
if (loop_cnt % 2 == 0) rqd_num++;
}
}
Console.WriteLine("The even number with odd digit={0} ", rqd_num);
}
private bool IsOddDigit(int num)
{
bool odd_digit = false;
if (num < 10) odd_digit = true;
else if (num < 100) odd_digit = false;
else if (num < 1000) odd_digit = true;
else if (num < 10000) odd_digit = false;
else if (num < 100000) odd_digit = true;
return odd_digit;
}
public void Even_Number_With_Odd_Digits()
{
int number = 100000;
int loop_cnt = 0;
int rqd_num = 0;
for (; loop_cnt < number ; loop_cnt++)
{
if (IsOddDigit(loop_cnt))
{
if (loop_cnt % 2 == 0) rqd_num++;
}
}
Console.WriteLine("The even number with odd digit={0} ", rqd_num);
}
private bool IsOddDigit(int num)
{
bool odd_digit = false;
if (num < 10) odd_digit = true;
else if (num < 100) odd_digit = false;
else if (num < 1000) odd_digit = true;
else if (num < 10000) odd_digit = false;
else if (num < 100000) odd_digit = true;
return odd_digit;
}
We are looking for numbers that have an even number of digits (2 digits, 4 digits etc.) and only those that have odd digits in them. This code finds 650 such numbers between 1 and 100,000. You can pass any other limit that you want:
- CasaPanacea July 12, 2015bool isAllOddDigits(int number) { while (number > 0) { int digit = number % 10; if ((digit % 2) == 0) return false; number = number / 10; } return true; } int evenNumOfOddDigits(const int & maxNumber) { int count = 0; int powerOf10 = 1; while (true) { // Start with 2 digit odd number (e.g. 11) then 4 digit (1001) and so on int from = (int)pow(10, powerOf10) + 1; if (from > maxNumber) break; // Go up to next power of 10 int to = (int)pow(10, powerOf10 + 1); // From 11 to 99 then 1001 to 9999 and so on for (int i = from; i < to; i += 2) // Skip even numbers since then have an even digit if (isAllOddDigits(i)) count++; powerOf10 += 2; // Skip over numbers that don't have an even number of digits } return count; }