4848 console . log ( "Rotation count is: " , output ) ;
4949}
5050
51+ // Approach 3: Using Repeated Concatenation and Substring
5152
53+ {
54+ function rotationCountUsingConcat ( arrInput ) {
55+ const dupArray = arrInput . concat ( arrInput ) ;
56+ const sortedSubstr = dupArray . slice ( ) . sort ( ( a , b ) => a - b ) ;
57+ const rotCountVal = dupArray . indexOf ( sortedSubstr [ 0 ] ) ;
58+ return rotCountVal ;
59+ }
60+ const inputArr = [ 15 , 18 , 2 , 3 , 6 , 12 ] ;
61+ const output = rotationCountUsingConcat ( inputArr ) ;
62+ console . log ( "Rotation Count is:" , output ) ;
63+ }
5264
53- // Approach 3: Using Repeated Concatenation and Substring
65+ // Approach 4: Two-Pointer Approach
5466
5567{
56-
57- }
68+ function findRotationCount ( arr ) {
69+ let start = 0 ;
70+ let end = arr . length - 1 ;
71+
72+ while ( start <= end ) {
73+ if ( arr [ start ] <= arr [ end ] ) {
74+ return start ;
75+ }
76+
77+ let mid = Math . floor ( ( start + end ) / 2 ) ;
78+ let next = ( mid + 1 ) % arr . length ;
79+ let prev = ( mid + arr . length - 1 ) % arr . length ;
80+
81+ if ( arr [ mid ] <= arr [ next ] && arr [ mid ] <= arr [ prev ] ) {
82+ return mid ;
83+ }
84+
85+ // Decide the side to search
86+ if ( arr [ mid ] >= arr [ start ] ) {
87+ // The rotation point is in the right half
88+ start = mid + 1 ;
89+ } else {
90+ // The rotation point is in the left half
91+ end = mid - 1 ;
92+ }
93+ }
94+ return 0 ;
95+ }
96+ const rotatedArray = [ 4 , 5 , 6 , 7 , 1 , 2 , 3 ] ;
97+ const rotationCount = findRotationCount ( rotatedArray ) ;
98+ console . log ( "Rotation count:" , rotationCount ) ;
99+ }
0 commit comments