iCIMS Interview Question Senior Software Development Engineers
Country: United States
Interview Type: Written Test
It fails at N equal to 19:
N = 19, Power = 6.115909044841455E19, findNumTimes1Appears() = 0
You can save me some time checking your answers by writing some test cases. Try these for starters:
for (int i = 0; i < 49; ++i) {
System.out.println("N = " + i + ", Power = " + Math.pow(11, i) + ", findNumTimes1Appears() = " + findNumTimes1Appears(i));
}
int N;
N = 50; System.out.println("N = " + N + ", Power = " + Math.pow(11, N) + ", findNumTimes1Appears() = " + findNumTimes1Appears(N));
N = 100; System.out.println("N = " + N + ", Power = " + Math.pow(11, N) + ", findNumTimes1Appears() = " + findNumTimes1Appears(N));
N = 200; System.out.println("N = " + N + ", Power = " + Math.pow(11, N) + ", findNumTimes1Appears() = " + findNumTimes1Appears(N));
Also notice that for N=300, the pow() function overflows.
There is a simpler solution :). Just consider that 11 is actually (10 + 1) and suddenly it is trivial.
Instead of working with actual integer, we can use linkedlist to represent the number and calculate the pow. The order of the solution comes to be O(n^2)
public static int getCountDigit(int pow) {
if(pow == 0) return 1;
if(pow ==1) return 2;
int ret_count = 0;
LinkedList<Integer> number = new LinkedList<Integer>();
number.add(1);
number.add(1);
for(int i = 1; i < pow; i++) {
number.add(1);
int j = number.size() - 2;
int sum = 0;
int carry = 0;
while(j > 0) {
sum = number.get(j) + number.get(j - 1);
number.set(j, ((sum % 10) + carry));
carry = sum / 10;
j--;
}
if(carry != 0) {
number.set(0, number.get(0) + carry);
}
}
for(int i = 0; i < number.size(); i++) {
if(number.get(i) == 1) {
ret_count++;
}
}
return ret_count;
}
public static int getCountDigit(int pow) {
if(pow == 0) return 1;
if(pow ==1) return 2;
int ret_count = 0;
LinkedList<Integer> number = new LinkedList<Integer>();
number.add(1);
number.add(1);
for(int i = 1; i < pow; i++) {
number.add(1);
int j = number.size() - 2;
int sum = 0;
int carry = 0;
while(j > 0) {
sum = number.get(j) + number.get(j - 1);
number.set(j, ((sum % 10) + carry));
carry = sum / 10;
j--;
}
if(carry != 0) {
number.set(0, number.get(0) + carry);
}
}
for(int i = 0; i < number.size(); i++) {
if(number.get(i) == 1) {
ret_count++;
}
}
return ret_count;
}
public static int getCountDigit(int pow) {
if(pow == 0) return 1;
if(pow ==1) return 2;
int ret_count = 0;
LinkedList<Integer> number = new LinkedList<Integer>();
number.add(1);
number.add(1);
for(int i = 1; i < pow; i++) {
number.add(1);
int j = number.size() - 2;
int sum = 0;
int carry = 0;
while(j > 0) {
sum = number.get(j) + number.get(j - 1);
number.set(j, ((sum % 10) + carry));
carry = sum / 10;
j--;
}
if(carry != 0) {
number.set(0, number.get(0) + carry);
}
}
for(int i = 0; i < number.size(); i++) {
if(number.get(i) == 1) {
ret_count++;
}
}
return ret_count;
}
Check this out:
public class Count {
public static void main(String[] args) {
countOnes(1000);
}
public static int countOnes(int power){
int count = 0;
if(power < 2){
count = power + 1;
} else{
StringBuilder number = new StringBuilder("11");
while((--power) > 0){
char [] charArray = number.toString().toCharArray();
int carry = 0;
number = new StringBuilder(""+charArray[charArray.length-1]);
for (int i = charArray.length-1; i > 0 ; i--) {
int temp = Integer.parseInt(""+charArray[i]) + Integer.parseInt(""+charArray[i-1]) + carry;
carry = temp/10;
temp = temp%10;
number.append(temp);
}
number.append(Integer.parseInt(""+charArray[0])+carry);
number.reverse();
}
Pattern pattern = Pattern.compile("1");
Matcher matcher = pattern.matcher(number);
while(matcher.find()){
count++;
}
}
return count;
}
}
import java.util.*;
public class ElevenPowN {
static Scanner in=new Scanner(System.in);
public static void main(String[] args)
{
long pow,val=11,rem = 1,count=0;
System.out.println("Enter the power :");
pow=in.nextInt();
for(int i=1;i<=pow;i++)
{
val=val*11;
}
while(rem!=0)
{
rem=val%10;
if(rem==1) count++;
val=val/10;
}
System.out.println("The number of one's are : "+count);
}
}
static int CountOfDigitOne(int N, out string l)
{
int c = 0;
string prev = "11";
string current = string.Empty;
for (int i = 2; i <= N; i++)
{
int rem = 0;
current = string.Empty;
for (int j = prev.Length -1 ; j > 0; j--)
{
int digit = prev[j] - '0';
int digit2 = prev[j - 1] - '0';
int n = digit + digit2 + rem;
if (n >= 10)
{
rem = 1;
n -= 10;
}
current = n + current;;
}
current += prev[prev.Length - 1];
current = prev[0] + current;
prev = current;
}
if (N == 0)
{
current = "1";
}
else if (N == 1)
current = "11";
for (int i = 0; i < current.Length; i++)
{
if (current[i] == '1')
c++;
}
l = current;
return c;
}
static int CountOfDigitOne(int N, out string l)
{
int c = 0;
string prev = "11";
string current = string.Empty;
for (int i = 2; i <= N; i++)
{
int rem = 0;
current = string.Empty;
for (int j = prev.Length -1 ; j > 0; j--)
{
int digit = prev[j] - '0';
int digit2 = prev[j - 1] - '0';
int n = digit + digit2 + rem;
if (n >= 10)
{
rem = 1;
n -= 10;
}
current = n + current;;
}
current += prev[prev.Length - 1];
current = prev[0] + current;
prev = current;
}
if (N == 0)
{
current = "1";
}
else if (N == 1)
current = "11";
for (int i = 0; i < current.Length; i++)
{
if (current[i] == '1')
c++;
}
l = current;
return c;
}
I took a different approach to the problem.
power of 11 is a power of (x+1) where x = 10
( 10 + 1 ) * ( 10 + 1 )
or
(x + 1) * (x+1)
x2 + 2x + 1 ===> power of 2
x3 + 3x2 + 3x + 1 ===> power of 3
x4 + + 4x3 + 6x2 + 4x + 1 ===> power of 4
x5 + 5x4 + 10x3 + 10x2 + 5x + 1 ===> power of 5
The constants at each term of power of x is called binomial coefficient.
For x = 10, if the coefficient is 1 the final number will have a 1.
But if the coefficient is more than 10 we need to carry ahead and add to next power term.
The following code works fine for some numbers I tested and it does not calculate the actual number, so there will be no overflow.
unsigned int binomial_coefficient(int n, int k) {
if (k < 0 or k > n)
return 0;
if (k == 0 or k == n)
return 1;
k = std::min(k, n - k);
int c = 1;
for (int i=0; i < k; i++)
c = c * (n - i) / (i + 1);
return c;
}
unsigned int ones_in_power_of_eleven(int N) {
std::vector<unsigned int> binomial_coeffs(N+1);
for (int k=0; k <= N/2; ++k) {
unsigned int c = binomial_coefficient(N,k);
binomial_coeffs[k] = c; // binomial coefficients are symmetric
binomial_coeffs[N-k] = c;
}
for (int i=0; i < N; i++) {
unsigned int coeff = binomial_coeffs[i];
unsigned int cahead = coeff / 10;
unsigned int remainder = coeff % 10;
binomial_coeffs[i] = remainder;
binomial_coeffs[i+1] += cahead;
}
int ones = 0;
for (int i=0; i <= N; i++) {
if (binomial_coeffs[i] == 1)
ones++;
}
return ones;
}
It's very interesting solution. I didn't expect to see binomial coefficients here :).
But what about complexity.
As I can see time complexity is O(N^2) and memory consumption is O(N).
On the other hand the solution where we the number is represented as a container of digits (for example, getCountDigit() method posted by bhanu.ashwani above) has the same time and memory characteristic. IMHO, that solution is more straightforward and obvious than this.
Correct me about solution comparing if I am wrong.
In this special case of (x+1)^N
if we have binomial coefficient == 1, the number will have a 1 in it.
This program used this property to calculate number of 1's in the final number without calculating the number.
unsigned int binomial_coefficient(int n, int k) {
if (k < 0 or k > n)
return 0;
if (k == 0 or k == n)
return 1;
k = std::min(k, n - k);
int c = 1;
for (int i=0; i < k; i++)
c = c * (n - i) / (i + 1);
return c;
}
unsigned int ones_in_power_of_eleven(int N) {
std::vector<unsigned int> binomial_coeffs(N+1);
for (int k=0; k <= N/2; ++k) {
unsigned int c = binomial_coefficient(N,k);
binomial_coeffs[k] = c; // binomial coefficients are symmetric
binomial_coeffs[N-k] = c;
}
for (int i=0; i < N; i++) {
unsigned int coeff = binomial_coeffs[i];
unsigned int cahead = coeff / 10;
unsigned int remainder = coeff % 10;
binomial_coeffs[i] = remainder;
binomial_coeffs[i+1] += cahead;
}
int ones = 0;
for (int i=0; i <= N; i++) {
if (binomial_coeffs[i] == 1)
ones++;
}
return ones;
}
As the last comments recommended using pascal triangle would help. I use different way fo calculating the coefficients. I used the literal mathematical formula but the C implementation by @DattaP is more efficient. Here is my Java Code:
class Problem{
public int solution(int N){
int carry=0;
int counter=0;
for(int i=0;i<N;i++){
int term= choose(N,i)+carry;
if((term%10)==1)
counter++;
carry=term/10;
}
return counter;
}
int choose(int n, int k){
return (factorial(n))/(factorial(k)*factorial(n-k));
}
int factorial(int n){
int result=1;
for(int i=1;i<=n;i++)
result*=i;
return result;
}
}
}
I've used BigInteger to arrive at the solution. Please comment.
package find.ones.eleven;
import java.math.BigInteger;
public class FindOnes {
public static void main(String[] noargs) {
System.out.println("Output: " + findOnes(1000));
}
public static int findOnes(int in) {
BigInteger b = BigInteger.valueOf(11);
System.out.println("Input: " + b.toString());
BigInteger bout = b.pow(in);
System.out.println("[DEBUG] 11^" + in + ": " + bout.toString());
char[] carray = bout.toString().toCharArray();
int count = 0;
for(int i = 0; i < carray.length; ++i) {
if(carray[i] == '1') {
++count;
}
}
return count;
}
}
power(11,N) can be calculated as below.
11
121
1331
14641
161051
1771561
19487171
private static int getNoOfOne(int N){
if (N==0) return 0;
else if (N==1) return 2;
else{
int[][] a=new int[N][N+1];
a[0][0]=1;
a[0][1]=1;
for(int i=1;i<N;i++){
a[i][0]=1;
a[i][N]=1;
for(int j=1;j<N;j++){
a[i][j]=a[i-1][j-1]+a[i-1][j];
if(a[i][j]>=10){
a[i][j-1]+=1;
a[i][j]=a[i][j]%10;
}
}
}
int count=0;
for(int x:a[N-1]){
if(x==1) count++;
}
return count;
}
class SolutionNumberOfOnesAppearsInElevenPowerN {
public int getNumberOneInElevenPowerN(int n) {
long num = (long) Math.pow(11, n);
long div = (long) Math.pow(10, n);
int count = 0;
System.out.print("(11 ^ " + n + "): " + num + " \t NUMBER OF 1 : " );
while(num != 0) {
if(num/div == 1) {
count++;
}
num = num % div;
div = div/10;
}
System.out.print(count);
System.out.println();;
return count;
}
}
public class NumberOfOnesAppearsInElevenPowerN {
public static void main(String[] args) {
SolutionNumberOfOnesAppearsInElevenPowerN sol = new SolutionNumberOfOnesAppearsInElevenPowerN();
sol.getNumberOneInElevenPowerN(0);
sol.getNumberOneInElevenPowerN(1);
sol.getNumberOneInElevenPowerN(2);
sol.getNumberOneInElevenPowerN(3);
sol.getNumberOneInElevenPowerN(4);
sol.getNumberOneInElevenPowerN(5);
sol.getNumberOneInElevenPowerN(6);
sol.getNumberOneInElevenPowerN(7);
sol.getNumberOneInElevenPowerN(8);
sol.getNumberOneInElevenPowerN(9);
sol.getNumberOneInElevenPowerN(10);
sol.getNumberOneInElevenPowerN(11);
sol.getNumberOneInElevenPowerN(12);
}
}
import java.util.*;
public class ElevenPowN {
static Scanner in=new Scanner(System.in);
public static void main(String[] args)
{long pow,val=11,rem = 1,count=0;
System.out.println("Enter the power :");
pow=in.nextInt();
for(int i=1;i<=pow;i++)
{val=val*11;}
while(rem!=0)
{ rem=val%10;
if(rem==1) count++;
val=val/10; }
System.out.println("The number of one's are : "+count);}}
Your solution appears to fail at N = 11. Your code above finds the number of 1's to be 1 but it is obviously 4. Did you unit test?
- robertlaub April 17, 2015N = 11, Power = 2.85311670611E11, findNumTimes1Appears(11) = 1