We have studied the structure of Si(112):Ga-(Nx1) reconstructions using atomic-resolution scanning tunneling microscopy and first-principles calculations. The nanofaceted clean Si(112) surface becomes planar following the adsorption of Ga, which forms long chains on the surface interrupted by isolated quasi-periodic defects. The defects create a mixture of (Nx1) structures (N~4-7) with 5x1 and 6x1 unit cells most common. We demonstrate that this structure consists of a chain of Ga atoms adsorbed at the (111)-like step edge within the (112) unit cell, and that the defects are Ga vacancies where the exposed step edge Si atoms form a dimer bond. Calculations performed as a function of vacancy period confirm that the surface energy is minimized at N=5-6, when compressive strain associated with the Si-Ga bonds is effectively minimized.