CareerCup

Why do people just post code that too without preserving white spaces and no documentation?
This forum really needs more discipline like stackoverflow.com. Admin, are you reading this?

#include <iostream>

bool is_eq_sum(int c_st, int c_n,
			   int a_st, int a_n,
			   int b_st, int b_n, char *dig);

bool is_addseq (int k, int n_k, int& ls1_st, int& ls1_n,
				int & ls2_st, int& ls2_n,char * dig);
void print_num(int last_1_st, int last_1_n,char * dig);
void print_seq(int last_1_st,int last_1_n,
			   int last_2_st,int last_2_n,char * dig);


int main (int argc, char * const argv[]) {
    // insert code here...
    
	int ndig=15;
	char dig[] = {1,2,1,2,2,4,3,6,6,0,9,6,1,5,6};
	
	
	int last_1_st;
	int last_1_n;
	int last_2_st;
	int last_2_n;
	
	for (int i=2;i<ndig;i++)
		
	if (is_addseq(i, ndig, last_1_st, last_1_n,
				  last_2_st, last_2_n, dig))
	{
		std::cout<<"Solution found\n";
		print_seq(last_1_st, last_1_n,
				  last_2_st, last_2_n, dig);
		print_num(last_2_st, last_2_n, dig);
		print_num(last_1_st,last_1_n,dig);
	}
	
	
	
	//delete [] dig;
	
    return 0;
}




bool is_addseq (int k, int n_k, int& ls1_st, int& ls1_n,
				int & ls2_st, int& ls2_n,char * dig)
{
    int last_1_st, last_2_st;
	int last_1_n, last_2_n;
	
	int n_c_dig = n_k-k;
	
		for (int i=0;i<k-1;i++)
		{	
			last_2_st=0;
			last_2_n=i+1;
			last_1_st=i+1;
			last_1_n = k-(i+1);
		if  (is_eq_sum(k, n_c_dig,
					   last_1_st, last_1_n,
					   last_2_st, last_2_n, dig))
		  {

			  ls2_st=last_1_st;
			  ls2_n=last_1_n;
			  ls1_st = k;
			  ls1_n = n_c_dig;
			  return true;
		  }
		}
	
	
	
	
	int a_init = 2;
	if (k-n_c_dig>2) a_init=k-n_c_dig;
	for (int i=a_init;i<k;i++)
	{

	if (is_addseq(i, k, last_1_st, last_1_n,
				   last_2_st, last_2_n, dig)) 
	{
		
		if  (is_eq_sum(k, n_c_dig,
					   last_1_st, last_1_n,
					   last_2_st, last_2_n, dig))
		
		{
			ls2_st=last_1_st;
			ls2_n=last_1_n;
			ls1_st = k;
			ls1_n = n_c_dig;
			return true;
			
		}
		
	}
	
	}
	return false;	


}




bool is_eq_sum(int c_st, int c_n,
			   int a_st, int a_n,
			   int b_st, int b_n, char *dig)
{

	if (c_n>a_n+1&&c_n>b_n+1) return false;
	if (a_n>c_n||b_n>c_n) return false;
	char * sum = new char [c_n];
	memset(sum, 0, c_n);
	char s_dig=0;
	char * i_a = dig + a_st + a_n-1;
	char * i_b = dig + b_st + b_n-1;
	char * i_s = sum + c_n-1;
	for (int i=0;i<c_n;i++,i_a--,i_s--,i_b--)
	{
		char d_s=0;
		if (i<a_n)
			d_s+=*i_a;
		if (i<b_n)
			d_s+=*i_b;
		d_s+=s_dig;
		if (d_s>9) {d_s-=10;s_dig=1;}
		else s_dig =0;
		*i_s = d_s;
	}
	
	
	if (s_dig) {delete [] sum;return false;}
	
	char *i_c = dig+ c_st;
	for (int i=0;i<c_n;i++)
		if (sum[i]!=i_c[i])
		{delete [] sum;return false;}
	
	delete [] sum;
	return true;
}

void print_num(int last_1_st, int last_1_n,char * dig)
{
	for (int i=last_1_st; i<last_1_st+last_1_n;i++)
		std::cout<<(int)dig[i];
	std::cout<<"\n";
}

void print_seq(int last_1_st,int last_1_n,
		  int last_2_st,int last_2_n,char * dig)
{
	if (last_2_st==0) return;
	for (int i=last_2_st-1,j=1;i>=0;i--,j++)
		if (is_eq_sum(last_1_st, 
					  last_1_n, 
					  last_2_st, 
					  last_2_n, 
					  i, j, dig))
		{
			print_seq (last_2_st, last_2_n,
					   i,j, dig);
			print_num(i, j, dig);
		}
	
}

My code, It can work:

public class Divide_Array {

public static ArrayList<Integer> return_results(int test){
String number=String.valueOf(test);
int[] array_int=new int[number.length()];
for(int i=0;i!=array_int.length;i++){
array_int[i]=Integer.valueOf(String.valueOf(number.charAt(i)));
}

ArrayList<Integer> results=new ArrayList<Integer>();

for(int i=0;i!=array_int.length;i++){
results.clear();
results.add(split(array_int,0,i));
compute_process(results,array_int,test,i+1);
if(isValid(results,test)){
return results;
}
}
return null;
}
public static void compute_process(ArrayList<Integer> results,int[] array_int,int aim,int step){
if(step==array_int.length){
return;
}
if(results.size()==1){
for(int i=step;i!=array_int.length;i++){
int next=split(array_int,step,i);
if(next==results.get(0)||next==results.get(0)+1){
results.add(next);
compute_process(results,array_int,aim,i+1);
if(isValid(results,aim)){
return;
}
}
}
}
else{
for(int i=step;i!=array_int.length;i++){
int next=split(array_int,step,i);
if(next==results.get(results.size()-1)+results.get(results.size()-2)){
results.add(next);
compute_process(results,array_int,aim,i+1);
if(isValid(results,aim)){
return;
}
}
}

}

}


public static int split(int[] test,int begin,int end){
if((begin<0)||(end>test.length-1)){
return Integer.MAX_VALUE;
}
int result=0;
for(int i=begin;i<=end;i++){
result*=10;
result+=test[i];
}
return result;
}


public static boolean isValid(ArrayList<Integer> test,int check){
if(test.size()<2){
return false;
}
if(test.size()==2){
if((test.get(1)!=test.get(0))&&(test.get(1)!=test.get(0)+1)){
return false;
}
String o1=String.valueOf(test.get(0))+String.valueOf(test.get(1));
String o2=String.valueOf(check);
if(o1.equals(o2)){
return true;
}
return false;
}
String o1=String.valueOf(test.get(0))+String.valueOf(test.get(1));
for(int i=2;i!=test.size();i++){
if(test.get(i)!=test.get(i-1)+test.get(i-2)){
return false;
}
o1+=String.valueOf(test.get(i));
}
if(o1.equals(String.valueOf(check))){
return true;
}
return false;
}


public static void main(String[] args) {
int test=1235813;
ArrayList<Integer> results=return_results(test);
if(results!=null){
for(int i=0;i!=results.size();i++){
System.out.println(results.get(i)+" ");
}
}
else{
System.out.println("OPPS");
}

}

}

Hi, I rewrote the program in another way. The time complexity now becomes O(NlgN) given N is the integer values of the upper bound.

#include <iostream>


void increase (char **dig_p, int & ndig);

bool is_lt(char *a, int na, char *b, int nb);
bool is_st(char *a, int na, char *b, int nb);
void sum_int (char *cr_p, int& nd_c,
			  char * last_1,int nd_1,
			  char *last_2,int nd_2);
void print_num(int last_1_st, int last_1_n,char * dig);

int main (int argc, char * const argv[]) {
    
    
	
	char start[1024];
	char end[1024];
	std::cout<<"Please input lower bound:\n";
	std::cin>>start;
	std::cout<<"Please input upper bound:\n";
	std::cin>>end;
	int nd_max = strlen(end);
	int nd_min = strlen(start);
	
	for (int i=0;i<nd_min;i++)
		start[i]=start[i]-'0';
	for (int i=0;i<nd_max;i++)
		end[i]=end[i]-'0';
	
	print_num(0, nd_min, start);
	print_num(0, nd_max, end);
	
	char num_store_1[1024];
	char num_store_2[1024];
	char last_2[1024];
	char last_1[1024];
	char cr[1024];
	char *cr_p=cr;
	char output[1024];
	char *out_p=output;
	
	char *num_1 = num_store_1 +1023;
	char *num_2 = num_store_2 +1023;
	num_1[0]=1;
	num_2[0]=1;
	int nd_1 =1;
	int nd_2=1;
	int nd_c,nd_t;
	int nd_ls1,nd_ls2;
	int h_nd_max=nd_max/2;
	
	while (nd_2<=h_nd_max)
	{
		
		
		
		num_1 = num_store_1 +1023;
		num_1[0]=1;
		nd_1 =1;
		while (nd_1<=h_nd_max)
		{
			

			memcpy(last_2, num_2, nd_2);
			memcpy(last_1, num_1, nd_1);
			memcpy(out_p, num_2, nd_2);
			memcpy(out_p+nd_2, num_1, nd_1);
			nd_ls2=nd_2;
			nd_ls1=nd_1;
			nd_t =nd_1+nd_2;
			
			while (nd_t<=nd_max)
			{

				sum_int (cr_p, nd_c, last_1, nd_ls1, last_2, nd_ls2);
				memcpy(out_p+nd_t, cr_p, nd_c);
				nd_t+=nd_c;
				
				if (nd_min==nd_t&&nd_max==nd_t)
				{
				  if (!is_st(out_p, nd_t, start, nd_min)&&
					  !is_lt(out_p, nd_t, end, nd_max))	
					  print_num(0, nd_t, out_p);
				}
				else if (nd_min==nd_t)
				{
					if (!is_st(out_p, nd_t, start, nd_min))
						print_num(0, nd_t, out_p);
				}
				else if (nd_max==nd_t)
				{
					if (!is_lt(out_p, nd_t, end, nd_max))
						print_num(0, nd_t, out_p);
				}
				else if (nd_min<nd_t&&nd_t<nd_max)
				{
					print_num(0, nd_t, out_p);
				}
				
				memcpy(last_2, last_1, nd_ls1);
				nd_ls2 = nd_ls1;
				memcpy(last_1, cr_p, nd_c);
				nd_ls1 = nd_c;
				
				
			}
			
			
			
			increase(&num_1, nd_1);
			//
		}
		
		increase(&num_2, nd_2);
	}
	
	
	return 0;
}

void increase (char **dig, int & ndig)
{
	
	int n=ndig-1;
	while (n>=0)
	{
		((*dig)[n])+=1;
		if ((*dig)[n]<10) break;
		else 
		{
			(*dig)[n]=0;
			n--;
		}
		
	}
	if (n<0) {(*dig)--;(*dig)[0]=1;ndig++;}
	
}


bool is_lt(char *a, int na, char *b, int nb)
{
	if (na>nb) return true;
	if (na<nb) return false;
	for(int i=0;i<na;i++)
		if (a[i]>b[i]) return true;
	return false;
}

bool is_st(char *a, int na, char *b, int nb)
{
	if (na>nb) return false;
	if (na<nb) return true;
	for(int i=0;i<na;i++)
		if (a[i]<b[i]) 
		{
			print_num(0, na, a);
			print_num(0, nb, b);
			std::cout<<"\n";
			return true;
		}
	return false;
}

void print_num(int last_1_st, int last_1_n,char * dig)
{
	for (int i=last_1_st; i<last_1_st+last_1_n;i++)
		std::cout<<(int)dig[i];
	std::cout<<"\n";
}

void sum_int (char *cr_p, int& c_n,
			  char * a_st,int a_n,
			  char *b_st,int b_n)
{
	char *cr = cr_p;
	int s_n = a_n>b_n ? a_n : b_n;
	char * sum = new char [s_n];
	memset(sum, 0, c_n);
	char s_dig=0;
	char * i_a = a_st + a_n-1;
	char * i_b = b_st + b_n-1;
	char * i_s = sum + s_n-1;
	for (int i=0;i<s_n;i++,i_a--,i_s--,i_b--)
	{
		char d_s=0;
		if (i<a_n)
			d_s+=*i_a;
		if (i<b_n)
			d_s+=*i_b;
		d_s+=s_dig;
		if (d_s>9) {d_s-=10;s_dig=1;}
		else s_dig =0;
		*i_s = d_s;
	}
	
	c_n = s_n;
	if (s_dig) {*(cr++)=1;c_n++;}

	
	for (int i=0;i<s_n;i++)
		cr[i]=sum[i];

	delete [] sum;
	
}

can any one explain the solution

any sequence {T(1),T(2),...T(n)} which satisfies T(n)=T(n-1)+T(n-2) is uniquely determined by n, T(1) and T(2). Thus we can generate any sequence in the range starting with the combination of any pair of T(1) and T(2). Here are two tricks. 1) the digit numbers of T(1) and T(2) cannot be larger than half of that of max range. 2) the digit numbers of sequence {T(1), T(2),...T(n)} must be inbetween those of min and max ranges.

tag

#include <iostream>
#include <math.h>

using namespace std;

int getLength(int n)
{
if (n==0) return 1;

int i = 0;

while (n >= pow(10,i))
{
i++;
}
return i;

}

void printAdditiveNumbers(int number, int one, int two, int low, int high)
{
int newNumber = number*pow(10,getLength(one+two))+one+two;
if (newNumber >= low && newNumber <= high)
{
cout << newNumber << endl;
printAdditiveNumbers(newNumber,two,one+two,low,high);
} else return;
}

void printAdditiveNumbers(int low, int high)
{
int oneU = getLength(high)/3; //maximum length for the first element in the sequence
int twoU = (getLength(high)-oneU)/2;
for (int i=1; i<=pow(10,oneU+1)-1; i++)
{
for (int j=0; j<=pow(10,twoU+1)-1; j++ )
{
printAdditiveNumbers(i*pow(10,getLength(j))+j, i, j, low, high);

}
}

for (int i=1; i<=pow(10,twoU+1)-1; i++)
{
for (int j=0; j<=pow(10,oneU+1)-1;j++)
{
printAdditiveNumbers(i*pow(10,getLength(j))+j, i, j, low, high);
}
}
}


int main(int argc, const char * argv[])
{
printAdditiveNumbers(1000,100000);
return 0;
}

public class AddativeNumber {

	public static void main(String[] args) {
		generator(123, 12412);
	}

	public static void generator(int start, int end) {

		for (int i = 1; i < end / 2; i++) {
			for (int j = 1; j < end / 2; j++) {
				fibonacci(start, end, i, j);
			}
		}
	}

	public static void fibonacci(int start, int end, int f, int s) {
		// f = 1;
		// s = 2;
		String res = Integer.toString(f) + Integer.toString(s);

		while (Integer.parseInt(res) < start) {
			int temp = f + s;
			res += temp;
			f = temp;
		}

		while (Integer.parseInt(res) < end) {
			int temp = f + s;
			res += temp;
			if (Integer.parseInt(res) < end)
				System.out.println(res);
			f = temp;
		}
	}
}

public class AddativeNumber {

	public static void main(String[] args) {
		generator(123, 12412);
	}

	public static void generator(int start, int end) {
		
		int halflength = (end + "").length() / 2;
		int maxgenerator = (int) Math.pow(10, halflength);

		for (int i = 1; i < maxgenerator; i++) {
			for (int j = 1; j < maxgenerator; j++) {
				fibonacci(start, end, i, j);
			}
		}
	}

	public static void fibonacci(int start, int end, int f, int s) {
		// f = 1;
		// s = 2;
		String res = Integer.toString(f) + Integer.toString(s);

		while (Integer.parseInt(res) < start) {
			int temp = f + s;
			res += temp;
			f = temp;
		}

		while (Integer.parseInt(res) < end) {
			int temp = f + s;
			res += temp;
			if (Integer.parseInt(res) < end)
				System.out.println(res);
			f = temp;
		}
	}
}