We introduce a new algorithm to reduce metal artifacts in computed tomography images when data is acquired using a single source spectrum. Our algorithm is a hybrid approach which corrects the sinogram vector followed by an iterative reconstruction. Many prior sinogram correction algorithms identify projection measurements that travel through areas with significant metal content, and remove those projections, interpolating their values for use in subsequent reconstruction. In contrast, our algorithm retains the information of random subsets of these metal-affected projection measurements, and uses an average procedure to construct a modified sinogram. To reduce the secondary artifacts created by this interpolation, we apply an iterative reconstruction in which the solution is regularized using a sparsifying transform. We evaluate our algorithm on simulated data as well as data collected using a medical scanner. Our experiments indicate that our algorithm reduces the extent of metal artifacts significantly, and enables accurate recovery of structures in proximity to metal.