Interview Question
Country: United States
Do the digits need to be unique? For example, can we say 1122 is a qulified number for N = 4? IOW, in your example, the relationship between ith and jth digits, where i < j, is '<', can it be '<='?
if all numbers are unique means allowed values for N are 1-9, and assuming positions range from 1-N (from left to right) here is a recursive solution. The main rule is the numbers allowed for ith position are i<->9-(N-i)
my solution uses lot of stack space than laxmi's because string object is sent from call-to-call.
BTW, initiating call should be printSeq(1, 0, s);
int N = 3;
void printSeq(int i, int prevValue, string pResult)
{
if(N<1 || N>9) return;
int lowEnd = prevValue + 1;
int highEnd = 9-(N-i);
if(highEnd < prevValue)
return;
for(;lowEnd<=highEnd;lowEnd++)
{
char ch = '0'+lowEnd;
stringstream temp;
string newResult;
temp << pResult;
temp << ch;
temp >> newResult;
if(newResult.length() == N)
cout<<newResult<<"\n";
else
printSeq(i+1, lowEnd, newResult);
}
}
import java.util.Stack;
public class QualifiedNumber {
// Prints qualified number sequence using numbers between start to end
// inclusive. The size of the sequence being equal to param : "digits"
static void printQualifiedNumbers(int start, int end, int digits,
Stack<Integer> stack) {
if (digits == 0) {
Stack<Integer> temp = new Stack<Integer>();
while (!stack.isEmpty()) {
temp.push(stack.peek());
stack.pop();
}
while (!temp.isEmpty()) {
System.out.print(temp.peek() + " ");
stack.push(temp.peek());
temp.pop();
}
System.out.println();
return;
}
for (int i = start; i <= end - digits + 1; ++i) {
stack.push(i);
printQualifiedNumbers(i + 1, end, digits - 1, stack);
stack.pop();
}
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<Integer>();
int START = 1;
int END = 9;
int digits = 4;
printQualifiedNumbers(START, END, digits, stack);
}
}
Sorry abt indentation:
import java.util.Stack;
public class QualifiedNumber {
/**
* Prints qualified number sequence using numbers between start to end
* inclusive. The size of the sequence being equal to "n"
*/
static void printQualifiedNumbers(int start, int end, int n,
Stack<Integer> stack) {
if (n == 0) {
Stack<Integer> temp = new Stack<Integer>();
while (!stack.isEmpty()) {
temp.push(stack.peek());
stack.pop();
}
while (!temp.isEmpty()) {
System.out.print(temp.peek() + " ");
stack.push(temp.peek());
temp.pop();
}
System.out.println();
return;
}
for (int i = start; i <= end - n + 1; ++i) {
stack.push(i);
printQualifiedNumbers(i + 1, end, n - 1, stack);
stack.pop();
}
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<Integer>();
int START = 1;
int END = 9;
int digits = 4;
printQualifiedNumbers(START, END, digits, stack);
}
}
There is also another iterative solution using bit maps, basically assuming N=9 and you want to print qualified numbers with n digits.
You keep track of bitmap having size N, with n set bits starting with all n lsb's set.
You can iteratively define
getNextBitMap(currentBitmap)
.
For each bitmap print the index of set bit starting from msb, each will be a qualified number.
#include <iostream>
void ascendingNumber(int N, int k, char a[])
{
if(k < N)
return;
if(N == 0)
printf("%s\n", a);
else {
for(int i = k; i >= N; i--)
{
a[N-1] = i + '0';
ascendingNumber(N-1, i-1, a);
}
}
}
void ascendingNumber(int n)
{
if(n > 9 || n < 0)
return;
char* a = new char[n+1];
ascendingNumber(n, 9, a);
delete[] a;
}
Here is a recrusive solution in c#
internal void NumberAsc()
{
NumberAsc(3, new StringBuilder(), 0);
}
private void NumberAsc(int n, StringBuilder sb, int lastDigit)
{
if (n == 0)
{
Console.WriteLine(sb.ToString());
return;
}
for (int i = 1; i <= 9; i++)
{
if (i > lastDigit)
{
sb.Append(i);
NumberAsc(n - 1, sb, i);
sb.Length = sb.Length - 1;
}
}
}
#include <iostream>
#define N 4
using namespace std;
void GenerateSubSetOfLength(int mainArr[], int subArr[], int n, int r, int maIndex, int saIndex)
{
if(maIndex > n) return;
if(saIndex > r)
{
for(int p = 0; p <=r; p++)
{
cout << " " << subArr[p];
}
cout<<endl;
}
else
{
if(maIndex <= n)
{
subArr[saIndex] = mainArr[maIndex];
GenerateSubSetOfLength(mainArr, subArr, n, r, maIndex+1, saIndex+1);
GenerateSubSetOfLength(mainArr, subArr, n, r, maIndex+1, saIndex);
}
}
}
int main()
{
int arr[9] = {1, 2, 3, 4, 5 ,6, 7, 8, 9};
int subArr[N];
GenerateSubSetOfLength(arr, subArr, 8, N-1, 0,0);
cout << endl;
return 0;
}
public static void main(String args[]) throws NumberFormatException, IOException
- learner November 29, 2011{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int length=Integer.parseInt(br.readLine());
getSequence(1,length,length,0,0);
}
public static void getSequence(int initial, int N, int length, int sum, int level) {
if(level==length)
{
System.out.println("sum"+sum);
return;
}
int temp=sum;
for(int i=initial;i<=9-N+1;i++)
{
sum=temp*10+i;
getSequence(i+1,N-1,length,sum,level+1);
}
}
A recursive solution. Suppose N=3..den the most significant digit can take values from 1 to 7, the second digit can take values from 2-8 when 1 is msb. So 9-N+1 keep track of values for a particular position