Bloomberg LP Interview Question
Financial Software Developers Software Engineer / DevelopersHi Shil, Your algorithm is correct, I have not gone through the program though. Just one thing you have to take care is the removing of those numbers which has leading zeros. Like for sum 1 (001..., 010...) and similarly for other sum.
Your approach is correct and in my opinion this is the way to go through.
Initial call : print("",0,0);
print(String a, int first3result, int last3result){
int len = a.length();
if(len<3){ // check if we are in first half of string
for(int i=0; i<=9; i++){
int firsthalfresult = first3result + i;
String forward = a+i;
print(forward, firsthalfresult, last3result); // only send result formed by placing new digit at this position at first half of our final digit.
}
}
else if(len>=3 && len<6){ // we already have first 3 digits at its place, and placing last part of number in place.
for( int i=0; i<=9 ; i++){
int lasthalfresult = last3result+i;
String forward = a+i;
print(forward, first3result, lasthalfresult);
}
}
else if(len == 6){ // our final number has been created and we have sum of first 3 digits and last 3 digits
if (first3result == last3result){
System.out.println(a);
}
}
}
}
The above function will print the number as string only if first three half result is equal to last three half result.
cool, thanks.
just an optimization,
in else if(len>=3 && len<6){
if first3result < last3result
return
#define BITS_IN_HALF_INT 32 //2 * 8 .. int is 4 bytes
int SumOf2HalfsAreEqual(int digits)
{
if(digits%2 || digits > BITS_IN_HALF_INT)
{
printf("Invalid i/p\n");
return -1;
}
else
{
int half = digits / 2;
int num = 10, start = 1;
while(half-- != 1)
{
start = num;
num = num * 10;
}
printf("Number of half's equal in %d digit number are : %d\n",digits, num-start);
return (num - start);
}
}
void first_half_equals_second_half()
{
for(int i = 100000; i <=999999; i++)
{
int first_half = i/1000;
int second_half = i%1000;
if (first_half == second_half )
cout <<i<<endl;
}
}
void fNum()
{
int a,b,j,k;
for(i=100000;i<=999999;i++)
{
a = i/1000;
b = i%1000;
j = Sum(a);
k = Sum(b);
if(j==k)
print(i);
}
}
int Sum(int a)
{
int sum=0;
while(a!=0)
{
sum = sum + a%10;
a = a/10;
}
return sum;
}
how about an algorithm something like this,
1. traverse from 100 to 999. Take this is as the first half ( 100 000 to 999 999 )
2. for each of the above given number, find all possible combination
Say, for 100 the other half could be 100 / 010 / 001
for 101 the other half could be 110 101 011 200 020 002
for 102 the other half could be 111 120 012 102 210 201 021 300 030 003
still some more logics are needed. I still need to think
Here is the output of the above sample code:
Sum of digits, number of occurance in first half, number of occurance in second half, total occurance respectively.
1 1 x 3 = 3
2 3 x 6 = 18
3 6 x 10 = 60
4 10 x 15 = 150
5 15 x 21 = 315
6 21 x 28 = 588
7 28 x 36 = 1008
8 36 x 45 = 1620
9 45 x 55 = 2475
10 54 x 63 = 3402
11 61 x 69 = 4209
12 66 x 73 = 4818
13 69 x 75 = 5175
14 70 x 75 = 5250
15 69 x 73 = 5037
16 66 x 69 = 4554
17 61 x 63 = 3843
18 54 x 55 = 2970
19 45 x 45 = 2025
20 36 x 36 = 1296
21 28 x 28 = 784
22 21 x 21 = 441
23 15 x 15 = 225
24 10 x 10 = 100
25 6 x 6 = 36
26 3 x 3 = 9
27 1 x 1 = 1
The result is 50412
Note that there are 900K six digits numbers and only about 50K satify the condition.
The above implementation loop through only 1K numbers as opposed to 900K numbers.
However it still has room to improve the algorithm as you may notice the number of occurance follow a pattern.
I would do somethig like this:
For each number between 0 to 27, find the number of ways of 3 numbers adding to that number, square them and sum them all;
The way u find the number of ways of summing numbers is through polynomail multiplication.
another possible solution is as below
//NOTE i have not compiled this code.
multimap<int,int> multimap;
for(i = 1 to 9 )
for(j = 1 to 9)
for(k = 1 to 9)
{
multimap[i + j + k] = (i*100+j*10+k);
}
//internally multimaps store the data in sorted order based on key
//so all the digit additions values will be stored in sorted order
//now get the iterators to traverse the multimaps and check for same digit addition values
multimap::iterator it;
multimap::iterator it2 = multimap.begin();
it2++; //make it point to 2nd map entry
for(it = multimap.begin();it2 != multimap.end();it2++)
{
if(it.first() == it2.first())
{
cout<<it.second()<<it2.second();
}
}
Here's a Python implementation. Got same answer 50412 as Shil:
def equal_digit_sums():
dists = {}
for i in range(1000):
digits = [int(d) for d in str(i)]
dsum = sum(digits)
if dsum not in dists:
dists[dsum] = [0,0]
dists[dsum][0 if len(digits) == 3 else 1] += 1
def prod(dsum):
t = dists[dsum]
return (t[0]+t[1])*t[0]
return sum(prod(dsum) for dsum in dists)
print(equal_digit_sums())
int count = 0;
for(int i = 100000; i< 999999; i++){
if(i/1000 == i%1000){
count ++;
}
}
System.out.println(count);
Correct version:
public class SumOfFirstThreeSameAsLastThree {
public static void main(String[] args) {
int count = 0;
for(int i = 100000; i< 999999; i++){
if(sumOfDigits(i/1000) == sumOfDigits(i%1000)){
System.out.println(i);
count ++;
}
}
System.out.println(count);
}
public static int sumOfDigits(int n){
int sum = 0;
while(n!=0){
sum += n%10;
n = n/10;
}
return sum;
}
}
Here is a math based one in C++.
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int main() {
for(int i = 1; i< 999999; i++) {
int num_digits = int(log(i)/log(10.0))+1;
int high = 1;
if (num_digits>3)
high = int(pow(10.0, num_digits-3));
if((i/high) == i%1000)
cout << i << endl;
}
return 0;
}
Sorry for the formatting. Here is the formatted one:
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int main() {
for(int i = 1; i< 999999; i++) {
int num_digits = int(log(i)/log(10.0))+1;
int high = 1;
if (num_digits>3)
high = int(pow(10.0, num_digits-3));
if((i/high) == i%1000)
cout << i << endl;
}
return 0;
}
Here is the real solution for the correct question. Sorry for reposts.
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int main() {
for(int i = 1; i< 999999; i++) {
int num_digits = int(log(i)/log(10.0))+1;
int power = 1;
if (num_digits>3)
power = int(pow(10.0, num_digits-3));
int high = i/power;
int low = i%1000;
int sum_high = high/100 + (high%100)/10 + (high%10);
int sum_low = low/100 + (low%100)/10 + low%10;
if(sum_high==sum_low)
cout << i << endl;
}
return 0;
}
I think we can do it using hash table.
for ( int i=0 to 9){
for( int j =0 to 9){
for(int k =0 to 9){
int v = i+j+k;
// Now hash this value v
}
}
}
Now we know that hash table will be having keys between 0 and 27.
Now for each key retrieve the corresponding set of numbers and their combination will give you the result.
public class SumOfFirstThreeSameAsLastThree {
public static void main(String[] args) {
for (int i = 0; i < 999999; i++)
if (checkSum(i))
System.out.println(i);
}
public static boolean checkSum(int n) {
// only 6 digits or more
if (n < 100000)
return false;
int begin = n / 1000, last = n % 1000;
// if the begin or last numbers are zero, there is no point to have a sum
if (begin == 0 || last == 0)
return false;
int sum1 = 0, sum2 = 0;
while (begin != 0 || last != 0) {
sum1 += begin % 10;
begin = begin / 10;
sum2 += last % 10;
last = last / 10;
}
return sum1 == sum2;
}
}
Check this out
printNo(int len,String no,int sum)
{
if(len==0){print no;}
if(len>3)
{
for(int i=0;i<9;i++){
if(len==6) continue;
for(int i=0;i<9;i++)
{
sum+=i;
no='0'+i;
printNo(len-1,no,sum);
}
else
{
for(int i=0;i<9;i++)
{
if(i>sum) break;
if(i + (len-1)*9 < sum) continue;
no += '0' + i;
sum-=i;
printNo(len-1,no,sum);
}
}
}
}
}
Opps a typo
printNo(int len,String no,int sum)
{
if(len==0){print no;}
if(len>3)
{
for(int i=0;i<9;i++){
if(len==6) continue;
if(len>3){
for(int i=0;i<9;i++)
{
sum+=i;
no='0'+i;
printNo(len-1,no,sum);
}
}
else
{
for(int i=0;i<9;i++)
{
if(i>sum) break;
if(i + (len-1)*9 < sum) continue;
no += '0' + i;
sum-=i;
printNo(len-1,no,sum);
}
}
}
}
}
The problem can be solved very easily by dynamic programming by just keeping track of which position are we filling currently and what is the sum of the digits filled till now.
int dp[6][28];
void init(){
for(int i=0;i<6;i++) for(int j=0;j<=27;j++) dp[i][j]=-1;
}
int no_solutions(int index=0,int sum=0){
if(index==6) return sum==0;
if(sum<0) return 0;
int &ans = dp[index][sum];
if(ans!=-1) return ans;
ans=0;
for(int i=((index==0)?1:0);i<10;i++){
if(index>2)
ans+=no_solutions(index+1,sum-i);
else
ans+=no_solutions(index+1,sum+i);
}
return ans;
}
main(){
init();
cout<<no_solutions()<<endl;
}
As we can see the code takes 10*27*6=1620 iterations to run The code can be very easily modified for a general n digit number!
int main()
{
int sum_1[27] = {0};
int sum_2[27]= {0};
for(int ii=1001; ii<2000; ii++)
{
int real_number = ii - 1000;
int third = real_number/100;
int second = (real_number%100)/10;
int first = (real_number%100)%10;
int s = third + second + first;
if(ii-1000>=100)
{
sum_2[s-1]++;
}
sum_1[s-1]++;
}
int total = 0;
for(int j=0; j<27; j++)
{
total += sum_1[j]*sum_2[j];
}
printf("%d\n", total);
}
int main()
{
int sum_1[27] = {0};
int sum_2[27]= {0};
for(int ii=1001; ii<2000; ii++)
{
int real_number = ii - 1000;
int third = real_number/100;
int second = (real_number%100)/10;
int first = (real_number%100)%10;
int s = third + second + first;
if(ii-1000>=100)
{
sum_2[s-1]++;
}
sum_1[s-1]++;
}
int total = 0;
for(int j=0; j<27; j++)
{
total += sum_1[j]*sum_2[j];
}
printf("%d\n", total);
}
If you analyse the problem you will see first three digits (i.e. first half) range from 100 to 999 and the next three digits (i.e. second half) range from 001 to 999. Also the sum of digits in both half range from 1 to 27.
So first find out how many number in both sides where sum of digits is 1 or 2 or... 27.
Once you find the number of occurance then multiply the corresponding occurance from both sides. Finally add the mutiplied value to get the result.
Here is sample code to do this:
- Shil November 26, 2009