GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Java/DynamicProgramming/CountNumBinaryStrings at master · dincoo/Java

Expand file tree

/

CountNumBinaryStrings

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
97 lines (83 loc) · 1.87 KB
/

CountNumBinaryStrings

Copy path

File metadata and controls

97 lines (83 loc) · 1.87 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
package DynamicProgramming;
/*
* here is a important algo in this we have to count
* maximum no. of different binary strings which doesnot have
* consectuive 1s
Test Case:
int n=30;
startAlgo();
System.out.println(numStrIS(n));
System.out.println(endAlgo()+"ms");
startAlgo();
CountNumBinaryStr out=new CountNumBinaryStr();
System.out.println(out.numStrR(n).ans);
System.out.println(endAlgo()+"ms");
startAlgo();
System.out.println(countStrings(n,0));
System.out.println(endAlgo()+"ms");
*/
public class CountNumBinaryStr {
public static long startTime;
public static long endTime;
public static void startAlgo() {
startTime=System.currentTimeMillis();
}
public static long endAlgo() {
endTime=System.currentTimeMillis();
return endTime-startTime;
}
public static int numStrIS(int n) {
int[] zeros=new int[n];
int []ones=new int[n];
//seed
zeros[0]=1;
ones[0]=1;
for(int i=1;i<n;i++) {
zeros[i]=zeros[i-1]+ones[i-1];
ones[i]=zeros[i-1];
}
int ans=zeros[n-1]+ones[n-1];
return ans;
}
private class Binary{
int ones;
int zeros;
int ans;
Binary(int ones,int zeros){
this.ones=ones;
this.zeros=zeros;
this.ans=0;
}
Binary(){}
}
public Binary numStrR(int n) {
if(n==1) {
Binary br=new Binary(1,1);
return br;
}
Binary mr=new Binary();
Binary rr=numStrR(n-1);
mr.zeros=rr.zeros+rr.ones;
mr.ones=rr.zeros;
mr.ans=mr.zeros+mr.ones;
return mr;
}
public static int countStrings(int n, int lastDigit)
{
if (n == 0) {
return 0;
}
// if only one digit is left
if (n == 1) {
return (lastDigit == 1) ? 1: 2;
}
// if last digit is 0, we can have both 0 and 1 at current pos
if (lastDigit == 0) {
return countStrings(n - 1, 0) + countStrings(n - 1, 1);
}
// if last digit is 1, we can have only 0 at current position
else {
return countStrings(n - 1, 0);
}
}
}
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.